线性同余方程

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

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

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

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

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

• 在方程

${\displaystyle 3x\equiv 2{\pmod {6}}}$

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

• 在方程

${\displaystyle 5x\equiv 2{\pmod {6}}}$

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

• 在方程

${\displaystyle 4x\equiv 2{\pmod {6}}}$

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

对于线性同余方程

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

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

举例来说，方程

${\displaystyle 12x\equiv 20{\pmod {28}}}$

中 ${\displaystyle 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 来说，所有的解就是 ${\displaystyle \{4,11,18,25\}}$ 。

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

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

${\displaystyle 2x\equiv 2{\pmod {6}}}$

${\displaystyle 3x\equiv 2{\pmod {7}}}$

${\displaystyle 2x\equiv 4{\pmod {8}}}$

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

${\displaystyle 9k\equiv -1{\pmod {7}}}$

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

${\displaystyle 42l\equiv -16{\pmod {8}}}$

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

${\displaystyle x\equiv 10{\pmod {84}}}$

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

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