线性同余方程

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

${\displaystyle ax\equiv b\ {\pmod {n}}\ \ \ \ (1)}$

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

${\displaystyle \{x_{0}+k{\frac {n}{d}}\mid k\in \mathbb {Z} \}.}$

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

例子

• 在方程

3x ≡ 2 (mod 6)

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

• 在方程

5x ≡ 2 (mod 6)

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

• 在方程

4x ≡ 2 (mod 6)

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

求特殊解

对于线性同余方程

ax ≡ b (mod n)      (1)

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

举例来说，方程

12x ≡ 20 (mod 28)

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

与线性丢番图方程的关系

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

线性同余方程组

线性同余方程组的求解可以分解为求若干个线性同余方程。比如，对于线性同余方程组：

2x ≡ 2 (mod 6)

3x ≡ 2 (mod 7)

2x ≡ 4 (mod 8)

首先求解第一个方程，得到x ≡ 1 (mod 3)，于是令x = 3k + 1，第二个方程就变为：

9k ≡ −1 (mod 7)

解得k ≡ 3 (mod 7)。于是，再令k = 7l + 3，第三个方程就可以化为：

42l ≡ −16 (mod 8)

解出：l ≡ 0 (mod 4)，即 l = 4m。代入原来的表达式就有 x = 21(4m) + 10 = 84m + 10，即解为：

x ≡ 10 (mod 84)

对于一般情况下是否有解，以及解得情况，则需用到数论中的中国剩余定理。

参见

• 同余方程
• 二次剩余
• 中国剩余定理
• 線性同餘方法