线性同余方程

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

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

其中是与的最大公约数。在模的完全剩余系中，恰有个解。

 例子 

 在方程

中， ，3 不整除 2，因此方程无解。 
 在方程

中， ，1 整除 2，因此方程在中恰有一个解：。
 在方程

中， ，2 整除 2，因此方程在中恰有两个解：以及。

 求特殊解 

对于线性同余方程
      (1)
若整除 ，那么为整数。由裴蜀定理，存在整数对（可用扩展欧几里得算法求得）使得，因此 是方程 (1) 的一个解。其他的解都关于与同余。

举例来说，方程

中  。注意到 ，因此 是一个解。对模 28 来说，所有的解就是  。

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

 线性同余方程组 

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

首先求解第一个方程，得到，于是令，第二个方程就变为：

解得。于是，再令，第三个方程就可以化为：

解出：，即 。代入原来的表达式就有 ，即解为：

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

 参见 

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

Category:同余
Category:方程