同餘

同餘（Congruence Modulo）係指兩個整數除另一個整數，呢兩個數嘅餘數都係一樣。喺現代嘅數學基礎中，同餘係一個等價關係。數學上，同餘會以「$\equiv$」表達。

考慮澌所有整數，除數（即模數）相同下、餘數亦相同嘅一羣整數就叫做「同餘類」。一個簡單例子係，${\text{ mod }}10$嘅同餘類就同啲整數嘅個位數對應（0: 10, 20... 1: 11, 21...）。

定義

如果兩個整數a、b係m嘅同餘既話，即係話a除m同b除m所得出嘅餘數係一樣。以數學表達嘅話即係：

$$a\equiv b{\text{ mod }}m\iff m|(a-b)\iff mz=a-b{\text{ for some }}z\in \mathbb {Z}$$

同餘有一個等價嘅定義，就係m係可以整餘到$a-b$。

例一

因為12同14除2都係餘0，所以可以寫成$12\equiv 14{\text{ mod }}2$。

證明

證明同餘係等價關係。根據「$\equiv$」嘅要求，就需要證明，自反性、對稱性、傳遞性。

• 自反性：($a\equiv a{\text{ mod }}m$) 一個整數除另一個整數嘅餘數係不變，所以$a\equiv a{\text{ mod }}m$。
• 對稱性：($a\equiv b{\text{ mod }}m\implies b\equiv a{\text{ mod }}m$) 如果a同b係m嘅同餘，$m|(a-b)$。

相對嘅定義係：$mz=a-b{\text{ for some }}z\in \mathbb {Z}$。

抽因式，抽個負出嚟，$m(-z)=b-a{\text{ for some }}z\in \mathbb {Z}$。

最後得出，$m|(b-a)\implies b\equiv a{\bmod {m}}$。

• 傳遞性：($a\equiv b{\bmod {m}}{\text{ and }}b\equiv c{\bmod {m}}\implies a\equiv c{\bmod {m}}$) 如果a同b係m嘅同餘，同時b同c又係m嘅同餘，即係$m|(a-b){\text{ and }}m|(b-c)$。

相對嘅定義係，$mx=a-b{\text{ for some }}x\in \mathbb {Z}$同埋$my=b-c{\text{ for some }}y\in \mathbb {Z}$。

將兩條式互相加埋得出，$m(x+y)=a-c{\text{ for some }}x,y\in \mathbb {Z}$。

最後得出，$m|(a-c)\implies a\equiv c{\bmod {m}}$。

因此，呢個係一個等價關係。

商餘計算

其實商餘同同餘嘅關係係密不可分。

計算規則

1. 如果$a\equiv b{\bmod {m}}$，有一個整數$k$，會令到$k+a\equiv k+b{\bmod {m}}$。
2. 如果$a\equiv b{\bmod {m}}$，有一個整數$k$，會令到$ka\equiv kb{\bmod {m}}$。

其實以上嘅規則係需要證明。呢兩條規則嘅意思係，同餘嘅方程係同普通嘅無分別，都係可以乘同埋除。不過有一點要注意嘅係$k$係整數，所以除法係唔存在。換句話嚟講，(2)係唔可以好似普通方程咁約簡。

同餘約簡

如果$na\equiv b{\bmod {m}}$，而$gcd(m,n)=1$嘅話，就會有一個整數$k$，會令到$a\equiv kb{\bmod {m}}$。變相將個n約走咗啦。

證明：利用比舒公式同埋輾轉相除法，知到會有整數$x,k\in \mathbb {Z}$符合$mx+ky=1$。

利用上面嘅公式，得知$mx=1-nk\implies 1\equiv nk{\bmod {m}}$。

如果將上面嘅n乘入去$na\equiv b{\bmod {m}}$，得到$kna\equiv kb{\bmod {m}}$。

因為同餘嘅傳遞性，$a\equiv kb{\bmod {m}}$。

同餘約簡可以係一個解線性商餘方程嘅工具。有關計算例子可以睇線性商餘方程。

應用

同餘可以證明一啲結果。例如：一個整數$n\in \mathbb {Z}$係可以被$3$整除，咁佢每個數字都可以被$3$整除。「$\iff$」

證明：

可以將$n$寫成$$n=a_{0}+10a_{1}+100a_{2}+\cdots$$$a_{0},a_{1},a_{2},\cdots$就係$n$嘅數字。

因為$10\equiv 1\mod 3$，所以$${\begin{aligned}n&\equiv a_{0}+10a_{1}+100a_{2}+\cdots \mod 3\\n&\equiv a_{0}+a_{1}+a_{2}+\cdots \mod 3\end{aligned}}$$。

睇埋

• 商餘
• 線性商餘方程
• 商餘計算