線性同餘方程

$ax\equiv b\pmod m$ 何時有解、有幾個?令 $d = \gcd(a,m)$:有解 ⟺ $d\mid b$;有解時在 $\bmod m$ 下恰有 $d$ 個解,彼此相差 $m/d$。

解法:$d = 1$ 時兩邊乘 $a$ 的模反元素;$d>1$ 時先把 $a, b, m$ 都除以 $d$,化成互質的情況解出 $x\equiv x_0\pmod{m/d}$,原方程在 $\bmod m$ 下的解就是 $x_0 + k\frac{m}{d}$,$k = 0, 1, \dots, d-1$。

算例:$3x\equiv4\pmod7$,$3^{-1}\equiv5$,$x\equiv20\equiv6$。$4x\equiv6\pmod{10}$:$d = 2\mid6$,化成 $2x\equiv3\pmod5$,$x\equiv4$,兩個解 $4, 9$。$4x\equiv5\pmod{10}$:$2\nmid5$,無解。

這是整數版的「解一次方程」,也是 Diophantine 方程 $ax + my = b$ 的另一種寫法;中國剩餘定理把多條這樣的方程合併;RSA 產生金鑰時求私鑰指數,就是解 $ed\equiv1\pmod{\varphi(N)}$ 這條線性同餘方程。