线性同余方程

线性同余方程把整数未知数放在模 $n$ 的运算中求解，标准形式为 $a x \equiv b (\mod n)$ ，其中 $n \geq 2$ ， $a, b$ 是已知整数。它的意思是 $n$ 整除 $a x - b$ ；求解的对象是模 $n$ 的剩余类，不是无穷多个形式不同的整数逐个罗列。

先检查最大公约数

取 $d = gcd (a, n)$ 。方程有解的充分必要条件是 $d ∣ b$ 。必要性很直接：若 $a x - b = k n$ ，那么 $b = a x - k n$ ，而 $d$ 同时整除 $a, n$ ，故整除 $b$ 。反过来，贝祖等式给出整数 $u, v$ 使 $a u + n v = d$ 。若 $b = d c$ ，两边乘以 $c$ ，便有 $a (u c) + n (v c) = b$ ，所以 $x = u c$ 是解。这一推导同时告诉我们如何用扩展欧几里得算法算出一个解。

当 $d ∣ b$ 时，可把方程中的 $a, b, n$ 同除以 $d$ ，得到 $\frac{a}{d} x \equiv \frac{b}{d} (\mod n / d) .$ 若 $n / d \geq 2$ ，由于 $gcd (a / d, n / d) = 1$ ， $a / d$ 在模 $n / d$ 下有模逆元，约化方程恰有一个模 $n / d$ 的解 $x_{0}$ 。若 $n / d = 1$ ，即 $n ∣ a$ ，原方程只问 $n ∣ b$ ：条件成立时全部整数都是解，可取 $x_{0} = 0$ 作为模 1 的代表，不必谈模 1 的逆元。回到原模数，全部 $d$ 个不同剩余类都是 $x_{0}, x_{0} + n / d, \dots, x_{0} + (d - 1) n / d$ 。当 $d = 1$ 时，原方程模 $n$ 恰有一个解。

解的个数也可以直接从差值看出来。若 $x$ 与 $x_{0}$ 都是原方程的解，则 $n ∣ a (x - x_{0})$ ，即 $n / d ∣ (a / d) (x - x_{0})$ 。由于 $a / d$ 与 $n / d$ 互素，可约去 $a / d$ ，得 $n / d ∣ x - x_{0}$ 。所以解之间的间距恰按 $n / d$ 的倍数变化；从 $x_{0}$ 开始每次加 $n / d$ ，加到第 $d$ 次才回到同一个模 $n$ 的剩余类。

算例：两个解与无解

求 $6 x \equiv 8 (\mod 14)$ 。因 $gcd (6, 14) = 2$ 且 $2 ∣ 8$ ，先约为 $3 x \equiv 4 (\mod 7)$ 。模 7 下 $3^{- 1} \equiv 5$ ，所以 $x \equiv 5 \cdot 4 \equiv 6 (\mod 7)$ ；模 14 的两个解是 $x \equiv 6, 13 (\mod 14)$ 。检验： $6 \cdot 6 = 36 \equiv 8$ ， $6 \cdot 13 = 78 \equiv 8 (\mod 14)$ 。若把右侧换成 9， $2 ∤ 9$ ，就没有解。

这里不能从 $6 x \equiv 8 (\mod 14)$ 直接“把两边除以 6”并保持模 14，因为 6 与 14 不互素，6 在该模数下没有逆元。正确的约去公因数会同时改变模数。这与普通整数等式的除法区别很大，也是解题时最容易漏掉多个解的地方。

整数方程与同余方程

方程 $a x \equiv b (\mod n)$ 还可写成 $a x - n y = b$ ，其中 $x, y$ 都是整数。这样它成为一个二元一次丢番图方程；贝祖等式立即解释可解条件 $gcd (a, n) ∣ b$ 。不过两者的答案形式不同：整数方程会列出无限组 $(x, y)$ ，同余问题只把 $x$ 按模 $n$ 不同的剩余类列出。回到 $6 x \equiv 8 (\mod 14)$ ，取 $x = 6$ 时有 $y = 2$ ，因 $6 \cdot 6 - 14 \cdot 2 = 8$ ；取 $x = 13$ 时有 $y = 5$ ，因 $6 \cdot 13 - 14 \cdot 5 = 8$ 。两个整数解对应前面两个不同的模 14 类。

自己再试 $15 x \equiv 9 (\mod 21)$ 。先算 $d = gcd (15, 21) = 3$ ，右端可被 3 整除；约为 $5 x \equiv 3 (\mod 7)$ 。模 7 下 $5^{- 1} \equiv 3$ ，故 $x \equiv 9 \equiv 2 (\mod 7)$ ，回到模 21 得 $x \equiv 2, 9, 16 (\mod 21)$ 。任选一个代入，如 $15 \cdot 16 = 240 \equiv 9 (\mod 21)$ ；另两类同样成立。若把右端改成 10，因 $3 ∤ 10$ ，不必继续求逆元即可判无解。

约去系数的陷阱

以 $2 x \equiv 2 (\mod 6)$ 为例，直接把两边除以 2 却仍写成 $x \equiv 1 (\mod 6)$ ，只留下 $x \equiv 1$ ，遗漏了 $x \equiv 4$ 。正确做法是同时把模数从 6 除以 2，得到 $x \equiv 1 (\mod 3)$ ；在模 6 下，这一类分成 $1, 4$ 两类。核验 $2 \cdot 1 = 2$ 、 $2 \cdot 4 = 8 \equiv 2 (\mod 6)$ 。只有 $gcd (a, n) = 1$ 时， $a$ 才能在保持模数 $n$ 不变的条件下约去。

再看一个解数较多的练习： $14 x \equiv 21 (\mod 35)$ 。先算 $d = gcd (14, 35) = 7$ ，于是约为 $2 x \equiv 3 (\mod 5)$ ；由于 $2^{- 1} \equiv 3 (\mod 5)$ ，得到 $x \equiv 9 \equiv 4 (\mod 5)$ 。把 4 每次加 5、直到模 35 开始重复，得到 $4, 9, 14, 19, 24, 29, 34$ 共七个解。取两端检查： $14 \cdot 4 = 56 \equiv 21 (\mod 35)$ ， $14 \cdot 34 = 476 \equiv 21 (\mod 35)$ 。这里不需要逐个试遍 0 到 34；先检查公约数，既决定能否求解，也预告解的个数。

处理负系数时可先换成同余的非负代表，例如 $- 3 x \equiv 2 (\mod 7)$ 与 $4 x \equiv 2 (\mod 7)$ 是同一方程，因为 $- 3 \equiv 4 (\mod 7)$ 。但这种替换只改变系数写法，不改变模数；它与上一段的“除以公因数并同时缩小模数”是两种不同操作。

把右侧取成零，还可得到一个简洁推论： $a x \equiv 0 (\mod n)$ 的模 $n$ 解恰有 $gcd (a, n)$ 个。它们从 $x = 0$ 开始，每次相差 $n / gcd (a, n)$ 。例如 $6 x \equiv 0 (\mod 14)$ 的解是 $0, 7$ 两类，而不是只剩零类。这个齐次方程的解数也能用来检查非齐次答案：若 $x_{0}$ 是 $a x \equiv b (\mod n)$ 的一个解，则每个其他解都可写成 $x_{0}$ 加上一个齐次方程的解；反之这样相加必仍满足原方程。

参考资料