線性商餘方程

線性商餘方程（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$，所以係有解。

睇埋

• 同餘
• 商餘
• 商餘計算
• 孫子定理
• 歐拉定理