线性同余方程

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：
:ax \equiv b \ \pmod{n} \ \ \ \ (1)

的方程。此方程有解当且仅当b能够被a与n的最大公约数整除（记作\gcd(a,n)|b）。这时，如果x_0是方程的一个解，那么所有的解可以表示为：
:\{x_0+k\frac{n}{d}\mid k\in\mathbb{Z}\}.

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

例子

• 在方程

:3x \equiv 2 \pmod{6}
中，d = \gcd(3,6) = 3 ，3 不整除 2，因此方程无解。

• 在方程

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

• 在方程

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

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

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

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

线性同余方程组
线性同余方程组的求解可以分解为求若干个线性同余方程。比如，对于线性同余方程组：
:2x \equiv 2 \pmod{6}
:3x \equiv 2 \pmod{7}
:2x \equiv 4 \pmod{8}

首先求解第一个方程，得到x \equiv 1 \pmod{3}，于是令x = 3k + 1，第二个方程就变为：
:9k\equiv -1 \pmod{7}

解得k\equiv 3 \pmod{7}。于是，再令k = 7l + 3，第三个方程就可以化为：
:42l\equiv -16\pmod{8}

解出：l\equiv 0\pmod{4}，即 l=4m。代入原来的表达式就有 x = 21(4m) + 10 = 84m + 10，即解为：
:x\equiv 10\pmod{84}

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

参见

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