2026 年吉林预赛

提示

先独立尝试，再展开工具说明与想法来源。

思路

Wilson 定理说素数 $p$ 下 $(p - 1)! \equiv - 1 (mod p)$ 。这里可用逆元配对解释：除 $1, - 1$ 外，非零类都与不同的逆元配成积1，余下积为-1。偶数模数不能直接套这个结论。

想法从哪来：尝试把所有项直接相乘会遇到零因子，得不到信息。先选一个素因子 $p$ ，比较输出中被 $p$ 整除的项数。输出为零当且仅当两个输入至少一个为零，而三组都要求同样多的零，迫使两组输入零位置完全重合。这样才能删掉相同位置，比较剩余非零项的乘积。奇模数下乘积符号发生矛盾；偶模数先照样对齐奇偶位置。若含因子4，共同偶数位置会生成过多的4倍数；若仅含一个因子2，就在共同奇数位置降到奇模数。每一步分类都在解决前一步无法直接使用的情况。

只比较总和不能固定逐项配对的影响。更稳定的信息是模素因子的零元位置与所有非零元的乘积。奇数模数可借 Wilson 定理直接矛盾；偶数模数先按是否被 $4$ 整除分类，余下的 $n = 2 m$ 情形再从共同的奇数位置降到奇模数 $m$ 。

解答

反设

z_{i} = x_{i} y_{i} (1 \leq i \leq n)

也构成模 $n$ 的完全剩余系。

情形一： $n$ 为奇数。

任取素因子 $p ∣ n$ ，令 $q = n / p$ 。一个模 $n$ 的完全剩余系约化到模 $p$ 后，每个模 $p$ 剩余类恰出现 $q$ 次。令

X_{0} = {i ∣ p ∣ x_{i}}, Y_{0} = {i ∣ p ∣ y_{i}} .

则 $∣ X_{0} ∣ = ∣ Y_{0} ∣ = q$ 。而 $p ∣ z_{i}$ 当且仅当 $i \in X_{0} \cup Y_{0}$ 。由于 ${z_{i}}$ 也应为完全剩余系，其中被 $p$ 整除的项恰有 $q$ 个，所以

∣ X_{0} \cup Y_{0} ∣ = q,

从而 $X_{0} = Y_{0}$ 。

在其余指标上， $x_{i}$ 模 $p$ 的每个非零剩余类各出现 $q$ 次， $y_{i}$ 亦然。由 Wilson 定理，

i \in / X_{0} \prod x_{i} \equiv ((p - 1)!)^{q} \equiv (- 1)^{q} (mod p),

对 $y_{i}$ 也有同样结论。因此

i \in / X_{0} \prod z_{i} \equiv (- 1)^{2 q} = 1 (mod p) . (3)

另一方面，若 ${z_{i}}$ 为完全剩余系，则其不被 $p$ 整除的项模 $p$ 也应使每个非零类各出现 $q$ 次，故

i \in / X_{0} \prod z_{i} \equiv ((p - 1)!)^{q} \equiv (- 1)^{q} (mod p) . (4)

$n$ 为奇数，所以 $p, q$ 都为奇数， $(4)$ 的右端为 $- 1$ ，与 $(3)$ 矛盾。故奇数 $n$ 时命题成立。

情形二： $4 ∣ n$ 。

每个模 $n$ 完全剩余系中恰有 $n /2$ 个偶数。令

X = {i ∣ 2 ∣ x_{i}}, Y = {i ∣ 2 ∣ y_{i}} .

则 $∣ X ∣ = ∣ Y ∣ = n /2$ ，且 $z_{i}$ 为偶数当且仅当 $i \in X \cup Y$ 。若 ${z_{i}}$ 为完全剩余系，其中偶数也恰有 $n /2$ 个，故

X = Y .

于是对这 $n /2$ 个共同指标， $x_{i}, y_{i}$ 都为偶数，因而 $4 ∣ z_{i}$ 。但当 $4 ∣ n$ 时，一个模 $n$ 完全剩余系中只有 $n /4$ 个数被 $4$ 整除，矛盾。

情形三： $n = 2 m$ ，其中 $m$ 为奇数。

这里由 $n \geq 3$ 知 $m \geq 3$ 。仍由上一情形开头的奇偶计数可知， $x_{i}$ 与 $y_{i}$ 为奇数的指标集合必须相同，记为 $I$ ；它恰有 $m$ 个元素，并且这些指标也正是 $z_{i}$ 为奇数的全部指标。

模 $2 m$ 的所有奇数剩余类在约化模 $m$ 后，恰好得到模 $m$ 的一个完全剩余系。因此

{x_{i} mod m ∣ i \in I}, {y_{i} mod m ∣ i \in I}

分别是模 $m$ 的完全剩余系。若 ${z_{i}}$ 是模 $2 m$ 的完全剩余系，则它的全部奇数项约化模 $m$ 后也构成完全剩余系，即

{x_{i} y_{i} mod m ∣ i \in I}

是模 $m$ 的完全剩余系。这与已经证明的奇数模数情形（ $m \geq 3$ ）矛盾。

三种情形覆盖所有 $n \geq 3$ ，故

x_{1} y_{1}, x_{2} y_{2}, \dots, x_{n} y_{n} 不构成模 n 的完全剩余系 .

复核

奇数情形中，零类位置必须完全重合是乘积论证的关键；否则不能直接删除含零项的指标。当 $n = 2 m$ 时， $m$ 为奇数保证“模 $2 m$ 的奇数类到模 $m$ 的剩余类”是一一对应，而 $n \geq 3$ 排除了降到 $m = 1$ 的例外。

方法总结

完全剩余系的逐项乘积问题可先看某个素因子下的整除位置：输出零类数量最少，会迫使两个输入的零类位置重合。随后用非零剩余类乘积制造符号矛盾。对偶数模数，先利用奇偶位置对齐； $4 ∣ n$ 时比较 $4$ 的倍数个数， $n \equiv 2 (mod 4)$ 时则从共同奇数位置降阶到奇模数。

作答

解析

提示

思路

解答

复核

方法总结