模算數

模算數或稱同餘運算（英語：Modular arithmetic）是一個整數的算術系統，其中數字超過一定值後（稱為模或餘數）後會「捲回」到較小的數值，模算數最早是出現在卡爾·弗里德里希·高斯在1801年出版的《算術研究》一書中。

這個時鐘計時方式使用了模數為12的模算數

模算數常見的應用是在十二小時制，將一天分為二個以十二小時計算的單位。假設現在七點，八小時後會是三點。用一般的算術加法，會得到7 + 8 = 15，但在十二小時制中，超過十二小時會歸零，不存在「十五點」。類似的情形，若時鐘目前是十二時，二十一小時後會是九點，而不是三十三點。小時數超過十二後會再回到一，為模12的模算數系統。依照上述的定義，12和12本身同餘，也和0同餘，因此12:00的時間也可以稱為是0:00，因為模12時，12和0同餘。

同餘關係

此章節介紹的是mod n的表示法。關於二元的mod運算，請見「模除」。

模算數可以在導入整數的同餘關係後，通過經典算數的運算法則來推導模運算的運算法則。若有兩個正整數${\displaystyle a}$和${\displaystyle b}$，並且二數的差值${\displaystyle a-b}$為${\displaystyle n}$的整數倍數，我們就可以說${\displaystyle a}$和${\displaystyle b}$在模${\displaystyle n}$下同餘。數學式表達為：^[1]

${\displaystyle a\equiv b{\pmod {n}}\,}$

例如

${\displaystyle 38\equiv 14{\pmod {12}}\,}$

因為38 − 14 = 24，是12的倍數。

上述的概念也對負數有效：

${\displaystyle {\begin{aligned}-8&\equiv 7{\pmod {5}}\\2&\equiv -3{\pmod {5}}\\-3&\equiv -8{\pmod {5}}.\end{aligned}}}$

而同餘關係也可以用計算帶餘除法中的餘數來理解。若正整數${\displaystyle a}$和${\displaystyle b}$在除以${\displaystyle n}$後的餘數相同，${\displaystyle a\equiv b{\bmod {m}}}$。例如：

${\displaystyle 38\equiv 14{\pmod {12}}\,}$

因為38和14除以12時，餘數都為2。這是因為38 − 14 = 24是12的整數倍。

運算定律

如果${\displaystyle a\equiv b{\pmod {n}}}$，${\displaystyle p\equiv q{\pmod {n}}}$，${\displaystyle c}$為任何正整數，

那麼我們有以下運算定律：^[2]

${\displaystyle a+c\equiv b+c{\pmod {n}}}$

${\displaystyle a-c\equiv b-c{\pmod {n}}}$

${\displaystyle ac\equiv bc{\pmod {n}}}$

${\displaystyle a^{c}\equiv b^{c}{\pmod {n}}}$

${\displaystyle a+p\equiv b+q{\pmod {n}}}$

${\displaystyle ap\equiv bq{\pmod {n}}}$

綜上所述，我們在模算數里可以使用除除法以外的任何四則運算。

應用

模算數在數論、群論、環論、紐結理論、抽象代數、計算機代數、密碼學、計算機科學及化學中都有使用^[3]，也出現在視覺藝術及音樂。

模算數是數論的基礎之一，也提供了群論、環論及抽象代數中一些重要的範例。

模算數也常作為識別碼的校驗碼。例如國際銀行賬戶號碼（IBAN）就用模97的餘數來避免輸入編號時的錯誤。

在密碼學中，模算數是 RSA及迪菲-赫爾曼等公開密鑰加密系統的基礎，也提到了和 橢圓曲線有關的有限域，用在許多的對稱密鑰算法中，包括高級加密標準（AES）、國際資料加密演算法（IDEA）、及RC4。RSA和迪菲-赫爾曼密鑰交換用到了模冪。

在電腦代數中，模算數常用來限制中間計算的整數係數大小，也限制計算中用到的資料。模算數用在多項式分解（英語：polynomial factorization）中（其中所有已知有效率的演算法都用到了模算數），而針對整數及有理數的多項式最大公因式（英語：polynomial greatest common divisor）、線性代數及Gröbner基（英語：Gröbner basis），最有效率解法都用到了模算數。

計算機科學中，模算數會以位操作的方式表示，也和其他定長度、循環式的數據結構有關。許多編程語言及計算器中都有模除，而XOR是二個位元在模2下的和。

化學中，表示化合物編號的CAS號，最後一碼是校驗碼，是將CAS號前二位數乘以1、下一位乘以2，再下一位乘以3……，最後對10取餘數而得。

音樂上，模12的模算數用在十二平均律的系統中，其中有純八度及異名同音的情形（例如升音符的C音和降音符的D音會視為是同一個音）。

去九法是徒手計算時快速的檢查工具，是以模9的模算數為基礎，而且其中最重要的性質是${\displaystyle 10\equiv 1{\pmod {9}}}$。

模7的模算數在許多計算特定日期是星期幾的演算法中出現，特別是蔡勒公式及判決日法則（英語：doomsday algorithm）中。

模算數也用在像法律（像分配 (政治)）、經濟學（像博弈論），若一些社會科學的分析會強調資源的比例分割（英語：Proportional (fair division)）及分配，也會用到模算數。

歷史背景

模算數的系統化發展可追溯至德國數學家高斯（Carl Friedrich Gauss）於 1801 年出版的著作《算術研究》（Disquisitiones Arithmeticae）。在該書中，高斯首次明確引入了「同餘」（congruence）這一概念，並採用如下記號：

${\displaystyle a\equiv b{\pmod {n}}}$

他將此關係定義為：若整數 ${\displaystyle a}$ 與 ${\displaystyle b}$ 相減後能被 ${\displaystyle n}$ 整除，則稱 ${\displaystyle a}$ 與 ${\displaystyle b}$ 在模 ${\displaystyle n}$ 下同餘，即：

當且僅當 ${\displaystyle n\mid (a-b)}$

高斯的研究標誌著模運算正式成為數論的基礎語言之一。他在書中不僅探討了模的基本性質，也提出了許多與同餘相關的重要定理，例如歐拉定理、小費馬定理與二次剩餘定理，對後世的代數、數論與現代密碼學產生深遠影響。^[4]

值得注意的是，在高斯之前，東亞的數學文獻中已有模運算的早期應用。例如中國古代《孫子算經》便出現了類似「中國剩餘定理」的思想，其描述如下：

：今有物，不知其數。三三數之，剩二；五五數之，剩三；七七數之，剩二。問物幾何？

這正對應於現代的同餘組合：

${\displaystyle {\begin{cases}x\equiv 2{\pmod {3}}\\x\equiv 3{\pmod {5}}\\x\equiv 2{\pmod {7}}\end{cases}}}$（中國剩餘定理的形式）

該問題的解可由中國剩餘定理求得，是模算數應用於實際問題的早期範例之一。^[5]

相關條目

• 布爾環
• 環形緩衝區
• 同餘關係
• 除法
• 有限域
• 勒讓德符號
• 模冪
• 模反元素
• 模除
• 數論
• 皮薩諾周期（模n下的斐波那契序列）
• 原根
• 二次互反律
• 二次剩餘
• 兩元素布爾代數
• 和模算數有關的群論主題：
  • 循環群
  • 整數模n乘法群
• 其他和模算數有關的重要定理：
  • 卡邁克爾函數
  • 中國剩餘定理
  • 歐拉定理 (數論)
  • 費馬小定理
  • 拉格朗日定理 (群論)