線性商餘方程

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

方程約簡

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

證明：

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

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

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

餘數合集

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

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

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

可解性

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

證明：

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

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

因為${\displaystyle g|n}$同${\displaystyle g|a}$成立，所以${\displaystyle g|b}$。

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

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

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

睇埋

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