线性同余方程

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

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

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

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

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

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

对于线性同余方程

若 = gcd(, ) 整除 ，那么${\displaystyle \frac{b}{d}}$+=，因此 ${\displaystyle x=\frac{rb}{d}}$ 同余。

举例来说，方程

中 d = gcd(12,28) = 4 。注意到 ${\displaystyle 4=12\times <!--\; \times \; -->(-<!--\; -\; -->2)+28\times <!--\; \times \; -->1}$ ≡ 1 (mod 3)，于是令 = 3 + 1，第二个方程就变为：

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

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

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