線性商餘方程

線性商餘方程（Linear Equation Modulo n）意指處理同埋求 $ax\equiv b\mod n$ 嘅解，係數學入面數論嘅一個分支。解一個線性商餘系統嘅方法有孫子定理。而線性商餘方程都會引伸出好多唔同嘅數學問題。

方程約簡

如果 $\gcd(c,n)=1$ 同埋 $ac\equiv bc\mod n$ ，咁 $a\equiv b\mod n$ 。

證明：

根據商餘定義， $n|(ac-bc)=c(a-b)$ 。

因為 $\gcd(c,n)=1$ ，所以根據歐幾理得推論， $n|(a-b)$ 。

有咗以上嘅證明，得知線性方程（或者同餘方程），係可以約簡。

餘數合集（Complete Set of Residues）就係指將所有整數除以指定一個整數之後嘅餘數集合而成一個集。

喺抽象代數入面，一般會以 $\mathbb {Z} /n\mathbb {Z}$ 嚟代表。

例子：當 $n=5$ ，佢嘅餘數集合就係 $\{0,1,2,3,4\}$ 。

$ax\equiv b\mod n$ 有解 $\iff$ $\gcd(a,n)$ 可以除得盡 $b$ 。

證明：

設 $g=\gcd(a,n)$ ，

如果 $ax\equiv b\mod n$ 係有解，咁 $n|(ax-b)$ 。

因為 $g|n$ 同 $g|a$ 成立，所以 $g|b$ 。

如果 $g|b$ ，咁 ${\frac {n}{b}}|({\frac {a}{g}}x+{\frac {b}{g}})$ 。

咁 $ax\equiv b\mod n$ 有解 $\iff$ ${\frac {a}{g}}x\equiv {\frac {b}{g}}\mod {\frac {n}{g}}$ 有解。

因為 $\gcd({\frac {a}{g}},{\frac {n}{g}})=1$ ，所以係有解。