线性同余方程

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：

a x \equiv b (\mod n) (1)

的方程。此方程有解当且仅当 $b$ 能够被 $a$ 与 $n$ 的最大公约数整除（记作 $\gcd (a, n) | b$ ）。这时，如果 $x_{0}$ 是方程的一个解，那么所有的解可以表示为：

{x_{0} + k \frac{n}{d} ∣ k \in ℤ} .

其中 $d$ 是 $a$ 与 $n$ 的最大公约数。在模 $n$ 的完全剩余系 ${0, 1, \dots, n - 1}$ 中，恰有 $d$ 个解。

例子

在方程

3 x \equiv 2 (\mod 6)

中， $d = \gcd (3, 6) = 3$ ，3 不整除 2，因此方程无解。

在方程

5 x \equiv 2 (\mod 6)

中， $d = \gcd (5, 6) = 1$ ，1 整除 2，因此方程在 ${0, 1, 2, 3, 4, 5}$ 中恰有一个解： $x = 4$ 。

在方程

4 x \equiv 2 (\mod 6)

中， $d = \gcd (4, 6) = 2$ ，2 整除 2，因此方程在 ${0, 1, 2, 3, 4, 5}$ 中恰有两个解： $x = 2$ 以及 $x = 5$ 。

求特殊解

对于线性同余方程

a x \equiv b (\mod n)

(1)

若 $d = \gcd (a, n)$ 整除 $b$ ，那么 $\frac{b}{d}$ 为整数。由裴蜀定理，存在整数对 $(r, s)$ （可用扩展欧几里得算法求得）使得 $a r + s n = d$ ，因此 $x = \frac{r b}{d}$ 是方程 (1) 的一个解。其他的解都关于 $\frac{n}{d}$ 与 $x$ 同余。

举例来说，方程

12 x \equiv 20 (\mod 28)

中 $d = \gcd (12, 28) = 4$ 。注意到 $4 = 12 \times (- 2) + 28 \times 1$ ，因此 $x \equiv 5 \times (- 2) \equiv - 10 \equiv 4 (\mod 7)$ 是一个解。对模 28 来说，所有的解就是 ${4, 11, 18, 25}$ 。

与线性丢番图方程的关系

考虑 $a x \equiv b (\mod n)$ ，其等价于 $a x = b + y n$ （ $y$ 是整数），也就是线性丢番图方程。运用辗转相除法可以求得该方程的解，有无限多个；但是在原同余方程中，解的个数受到 $\gcd (a, n)$ 限制，因此正如上面例子所示，只能选取前面的几个解。