商餘計算

商餘計算（英文：Modular Arithmetic），或者叫做商餘數學，書面語可能叫做「模數學」，係數學入面一套特別嘅整數計算，早係1801年就已經喺高斯本書Disquisitiones Arithmeticae入面記載。

時鐘記時就係用商餘12運算。

可以利用「時鐘」嚟理解商餘計算，朝早9點加5個鐘就係下晝2點，喺個鐘上面會顯示由9變做2，其實就係因為9+5=14，而14除以12餘2。呢個就一個常見又易明嘅例子。

等價關係

内文：同餘

商餘計算主要集中喺同餘關係上面，而同餘係一個等價關係。用數字式嚟定義同餘呢個關係可以寫成：

$$a\equiv b{\bmod {m}}\iff m|(a-b)$$

呢個定義同加、減、乘呢三個運算都係兼容（compatible）嘅，用加法嚟做例子，就係如果有$a\equiv b{\pmod {m}}$同埋$c\equiv d{\pmod {m}}$，咁就可以推導出$a+c\equiv b+d{\pmod {m}}$。

假設揀定咗一個正整數$m$。「$a$同$b$係$m$嘅同餘」，數學式會寫做$a\equiv b{\bmod {m}}$。

例子：

$51\equiv 11{\bmod {5}}$

從普通角度了解就係，$51\div 5=10\cdots 1$同埋$11\div 5=2\cdots 1$。由此可見，佢哋嘅同餘都係1，所以喺同餘呢個關係上面，佢哋係一樣。

從定義嘅角度嚟睇，$51-11=40$。而40係可以被5除盡，即係$5|40=(51-11)$。因此符合定義。

同餘加法同乘法

内文：同餘

假設有兩個同餘關係，$a_{1}\equiv b_{1}{\bmod {m}}$ 同埋 $a_{2}\equiv b_{2}{\bmod {m}}$。可以得出：

• $a_{1}+a_{2}\equiv b_{1}+b_{2}{\bmod {m}}$
• $a_{1}-a_{2}\equiv b_{1}-b_{2}{\bmod {m}}$
• $a_{1}a_{2}\equiv b_{1}b_{2}{\bmod {m}}$

注意：同餘關係入面嘅除法同平時做嘅除法好唔同。

餘數定理嘅應用

内文：餘數定理

舉個例，利用餘數定理將16除3，得出$16=3\times 5+1$。因而得知，16除3嘅餘數係1。數學上會將「16除3嘅餘數係1」呢件事叫做商餘（mod），數學式會寫$16{\bmod {3}}=1$。

再舉多個例，$22{\bmod {3}}=1$因為$22=3\times 7+1$。如果跟返上面嘅定義，得知

$$22\equiv 16{\bmod {3}}$$

由此可見「$\equiv$」可以解做「${\text{mod}}$」，但係因為數學上唔止一個等價關係，所以會寫做「$\equiv _{m}$」嚟區別。而從同一個例子可以見到：

$$A\equiv B{\bmod {m}}\iff A{\bmod {m}}=B{\bmod {m}}$$

注意：左面嘅係「$\equiv$」，而右面嘅係「$=$」。

由上面嘅性質推斷落去，可以得知

$$(a{\bmod {m}})(b{\bmod {m}})\equiv ab{\bmod {m}}\iff ((a{\bmod {m}})(b{\bmod {m}})){\bmod {m}}=(ab){\bmod {m}}$$

證明：

$a{\bmod {m}}$，利用餘數定理即係有某啲整數$q\in \mathbb {Z}$符合，$r_{a}=a{\bmod {m}}=a-mq$。

$b{\bmod {m}}$，利用餘數定理即係有某啲整數$p\in \mathbb {Z}$符合，$r_{b}=b{\bmod {m}}=b-mp$。

$${\begin{aligned}r_{a}r_{b}&=(a-mq)(b-mp)\\&=ab-(a+b)mp+(mp)^{2}\\r_{a}r_{b}-(ab)&=m((a+b)p+mp^{2})\end{aligned}}$$

所以得出$m|(r_{a}r_{b}-(ab))\implies r_{a}r_{b}\equiv ab{\bmod {m}}$。

應用

如果$a,b\in \mathbb {Z}$係兩個整數，$p$係質數，咁$(a+b)^{p}\equiv a^{p}+b^{p}\mod p$。

睇埋

• 等價集合
• 商餘集合
• 整數商餘
• Checksum