线性同余方程

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

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}}

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

参见

检索自“https://zh.wikipedia.org/w/index.php?title=线性同余方程&oldid=75754076”