線性同餘方程

在數論中，線性同餘方程是最基本的同餘方程，「線性」表示方程的未知數次數是一次，即形如：

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

對於一般情況下是否有解，以及解得情況，則需用到數論中的中國剩餘定理。

參見

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