2026 年江苏预赛

提示

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

思路

乘法阶是最小的正整数 $d$ 使 $a^{d} \equiv 1$ ；模素数的原根能达到阶 $p - 1$ 。中国剩余定理允许在互素模数下同时指定余数。这两项是本解的课外工具，作用是把“所有单位”压成 $p - 1, q - 1 ∣ n - 2$ ；最后仍需逐模验证充分性。

想法从哪来：对与 $n$ 互质的 $a$ 先消去一个 $a$ ，把条件改成同一个指数总使单位变回1。要排除平方奇质因子，试选择“接近1”的单位 $a = 1 + n / p$ ，使二项式展开的高次项都被模数吸收，只留下一个能推出 $p ∣ 2$ 的线性条件。剩下两个奇质因子时，先用小模数控制2的指数，再用模素数的最大周期把全称条件压成整除式。设 $p < q$ 后，从 $q - 1 ∣ 2^{α} p - 2$ 引入整数商；分子与分母大小接近，商只有少数可能值，分类才变成可穷尽的检查，而非无界试素数。

原条件对单位元等价于 $a^{n - 2} \equiv 1 (mod n)$ 。第（1）问若假设 $p^{2} ∣ n$ ，取紧邻 $1$ 的单位 $1 + n / p$ ，二项式展开只留下线性项。第（2）问先由原根和中国剩余定理得到 $p - 1, q - 1 ∣ n - 2$ ，再把 $n = 2^{α} pq$ 代入； $α$ 只有 $1, 2, 3$ 三种，而较大的奇质因子 $q$ 使一个整数商只能取很少的奇数值，因而可以穷尽。

解答

对任意 $g cd (a, n) = 1$ ，题设等价于

a^{n - 2} \equiv 1 (mod n) . (1)

（1）反设 $p^{2} ∣ n$ ，令

a = 1 + \frac{n}{p} .

对 $n$ 的每个质因子 $r$ ，都有 $a \equiv 1 (mod r)$ ，故 $g cd (a, n) = 1$ 。又因 $(n / p)^{2}$ 是 $n$ 的倍数，二项式展开给出

a^{n - 1} \equiv 1 + (n - 1) \frac{n}{p} (mod n) .

由题设 $a^{n - 1} \equiv a (mod n)$ ，可得

n ∣ (n - 2) \frac{n}{p},

即 $p ∣ n - 2$ 。但 $p ∣ n$ ，所以 $p ∣ 2$ ，与 $p$ 为奇质数矛盾。因此

p^{2} ∤ n .

（2）设 $n$ 的两个奇质因子为 $p < q$ 。由第（1）问，可写成

n = 2^{α} pq (α \geq 0) . (2)

若 $α = 0$ ，则 $n - 2$ 为奇数。由中国剩余定理可取 $a \equiv - 1 (mod p)$ 、 $a \equiv 1 (mod q)$ ，这时 $g cd (a, n) = 1$ ，但式 (1) 模 $p$ 化为 $- 1 \equiv 1 (mod p)$ ，矛盾。因此 $α \geq 1$ 。

若 $α \geq 4$ ，由中国剩余定理可取

a \equiv 3 (mod 16), a \equiv 1 (mod pq) .

此时 $g cd (a, n) = 1$ ，且

n - 2 = 2 (2^{α - 1} pq - 1)

是 $2$ 乘以一个奇数。于是

a^{n - 2} \equiv 3^{2 \cdot 奇数} \equiv 9 \neq \equiv 1 (mod 16),

又与式 (1) 矛盾。所以

1 \leq α \leq 3. (3)

取模 $p$ 的原根，并利用中国剩余定理使它同时模 $n / p$ 为 $1$ ；由式 (1)，该原根的阶 $p - 1$ 必须整除 $n - 2$ 。同理 $q - 1 ∣ n - 2$ 。结合式 (2)，得到

p - 1 ∣ 2^{α} q - 2, q - 1 ∣ 2^{α} p - 2. (4)

反之，若式 (3)、(4) 成立，则对任意 $g cd (a, n) = 1$ ，费马小定理给出 $a^{n - 2} \equiv 1 (mod p)$ 及 $(mod q)$ ；同时 $a$ 为奇数、 $n - 2$ 为偶数，而任意奇数的平方模 $8$ 为 $1$ ，故也有 $a^{n - 2} \equiv 1 (mod 2^{α})$ 。由中国剩余定理，式 (1) 成立。因此式 (3)、(4) 是充分必要条件。

当 $α = 1$ 时，由式 (4)，

q - 1 ∣ 2 (p - 1) .

又 $q - 1 > p - 1$ ，故 $q - 1 = 2 (p - 1)$ ，即

q = 2 p - 1.

此时式 (4) 的另一条件自动成立。因此得到一族解

n = 2 p (2 p - 1), (5)

其中 $p$ 与 $2 p - 1$ 都是奇质数。

当 $α = 2$ 时，令

k = \frac{4 p - 2}{q - 1} .

由 $q > p$ 可知 $k < 4 + 2/ (p - 1) \leq 5$ ；又 $4 p - 2$ 恰含一个因子 $2$ ，而 $q - 1$ 为偶数，所以 $k$ 为奇数，故 $k = 1$ 或 $3$ 。由 $k (q - 1) = 4 p - 2$ 及 $p - 1 ∣ 4 q - 2$ ，可得

p - 1 ∣ k (4 q - 2) ⟹ p - 1 ∣ 2 (k + 4) .

若 $k = 1$ ，则 $p - 1 ∣ 10$ ，检验得到 $(p, q) = (3, 11), (11, 43)$ ；若 $k = 3$ ，则 $p - 1 ∣ 14$ ，没有符合式 (4) 的质数对。因此

n = 132, 1892. (6)

当 $α = 3$ 时，令

k = \frac{8 p - 2}{q - 1} .

$p = 3, 5$ 可直接检验；当 $p \geq 7$ 时，由 $q > p$ 及奇偶性知 $k \in {1, 3, 5, 7}$ 。与上面同样地，由式 (4) 得

p - 1 ∣ 6 (k + 8) . (7)

式 (7) 给出的有限候选分别为

k 1357 p 的候选（含合数，检验时剔除） 3, 7, 19, 55 3, 7, 23, 67 3, 7, 27, 79 3, 7, 11, 19, 31, 91 最终满足式 (4) 的 (p, q) (3, 23), (19, 151) (7, 19) (79, 127) 无

例如 $k = 3, p = 67$ 虽给出质数 $q = 179$ ，但 $66 ∤ 8 \cdot 179 - 2$ ，故必须剔除。于是

n = 552, 1064, 22952, 80264. (8)

综合式 (5)、(6)、(8)，所有答案为

n = 2 p (2 p - 1) (p, 2 p - 1 均为奇质数), 132, 1892, 552, 1064, 22952, 80264 .

复核

第（1）问所取的 $a$ 确与 $n$ 互质，且二次及更高项均含因子 $(n / p)^{2}$ ，确为 $n$ 的倍数。第（2）问没有把必要条件误当成充分条件：式 (4) 连同 $1 \leq α \leq 3$ 已逐模 $2^{α}, p, q$ 证明充分。表中每一对代回式 (4) 均成立；式 (5) 中 $q - 1 = 2 (p - 1)$ ，两个整除关系也都成立。

方法总结

“对所有与模数互质的整数成立”的幂同余，应先转化为单位群的指数条件。平方奇质因子可用 $1 + n / p$ 的二项式展开排除；剩下的质因子指数条件可借助原根与中国剩余定理转化为 $p - 1 ∣ n - 2$ 。当未知质数有大小顺序时，把较大的 $q - 1$ 写成一个表达式的因子，会迫使商 $k$ 很小，从而把无限搜索变成可核查的有限分类。

作答

解析

提示

思路

解答

复核

方法总结