模算數

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

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

同餘關係

模算數可以在導入整數的同餘關係後，通过经典算数的运算法则来推导模运算的运算法则。若有两个正整数 $a$ 和 $b$ ，并且二數的差值 $a-b$ 為 $n$ 的整數倍數，我们就可以说 $a$ 和 $b$ 在模 $n$ 下同餘。数学式表达为：^[1]

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

例如

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

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

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

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

而同餘關係也可以用計算带余除法中的余数来理解。若正整数 $a$ 和 $b$ 在除以 $n$ 后的余数相同， $a\equiv b{\bmod {m}}$ 。例如：

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

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

运算定律

如果 $a\equiv b{\pmod {n}}$ ， $p\equiv q{\pmod {n}}$ ， $c$ 为任何正整数，

那么我们有以下运算定律：^[2]

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

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

ac\equiv bc{\pmod {n}}

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

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

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的模算數為基礎，而且其中最重要的性質是 $10\equiv 1{\pmod {9}}$ 。

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

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

參考資料

^ Emanuel Lazar. Math 170 lecture notes (PDF). UPenn: 73. April 30, 2016 [2021-10-23]. （原始内容存档 (PDF)于2021-10-23）.
^ Sandor Lehoczky; Richard Rusczky. David Patrick , 编. the Art of Problem Solving Vol. 1 7. : 44. ISBN 0977304566 （英语）.
^ Sharky Kesa; et al. Modular Arithmetic. Brillant. [2021-10-23]. （原始内容存档于2021-10-26）.

[1] Emanuel Lazar. Math 170 lecture notes (PDF). UPenn: 73. April 30, 2016 [2021-10-23]. （原始内容存档 (PDF)于2021-10-23）.

[2] Sandor Lehoczky; Richard Rusczky. David Patrick , 编. the Art of Problem Solving Vol. 1 7. : 44. ISBN 0977304566 （英语）.

[3] Sharky Kesa; et al. Modular Arithmetic. Brillant. [2021-10-23]. （原始内容存档于2021-10-26）.

[1]

[2]

[3]

同餘關係

运算定律

應用

相關條目

參考資料