基本介紹
- 中文名：線性同餘方程
- 簡介：最基本的同餘方程
- 概述：“線性”方程未知數次數是一次.
- 學科：數論
定義,例子,求特殊解,線性同餘方程組,參見,
定義
在數論中，線性同餘方程是最基本的同餘方程，“線性”表示方程的未知數次數是一次，即形如：
ax≡b (mod n)的方程。此方程有解若且唯若 b 能夠被 a 與 n 的最大公約數整除（記作 gcd(a,n) | b）。這時，如果 x0 是方程的一個解，那么所有的解可以表示為：
{x0+kn/d|(k∈z)}
其中 d 是a 與 n 的最大公約數。在模 n 的完全剩餘系 {0,1,…,n-1} 中，恰有 d 個解。
例子
* 在方程
3x ≡ 2 (mod 6)
中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程無解。
* 在方程
5x ≡ 2 (mod 6)
中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一個解: x=4。
* 在方程
4x ≡ 2 (mod 6)
中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有兩個解: x=2 and x=5。
求特殊解
對於線性同餘方程
ax ≡ b (mod n) (1)
若 d = gcd(a, n)，d 整除 b ，那么b/d為整數。由裴蜀定理，存在整數對 (r,s) （可用輾轉相除法求得）使得 ar+sn=d，因此 x0=rb/d是方程 (1) 的一個解。其他的解都關於n/d與 x 同餘。即x≡x0+(n/d)*t (mod n) (0≤t≤d-1)。
舉例來說，方程
12x ≡ 20 (mod 28)
中 d = gcd(12,28) = 4 。注意到 4 = 12 *(-2)+28*1，因此 x0≡5*(-2)≡-10≡4(mod 7)是一個解。對模 28 來說，t=1,x≡4+(28/4)*1≡11 (mod 28)；t=2,x≡4+(28/4)*2≡18 (mod 28)；t=3,x≡4+(28/4)*3≡25 (mod 28) 。所有的解就是 {4,11,18,25} 。
線性同餘方程組
線性同餘方程組的求解可以分解為求若干個線性同餘方程。比如，對於線性同餘方程組：
2x ≡ 2 (mod 6)
3x ≡ 2 (mod 7)
2x ≡ 4 (mod 8)
首先求解第一個方程，得到x ≡ 1 (mod 3)，於是令x = 3k + 1，第二個方程就變為：
9k ≡ −1 (mod 7)
解得k ≡ 3 (mod 7)。於是，再令k = 7l + 3，第三個方程就可以化為：
42l ≡ −16 (mod 8)
解出：l ≡ 0 (mod 4)，即 l = 4m。代入原來的表達式就有 x = 21(4m) + 10 = 84m + 10，即解為：
x ≡ 10 (mod 84)
