查看“︁模算數”︁的源代码

[[File:Clock group.svg|thumb|250px|right|這個時鐘計時方式使用了模數為12的模算數]]

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

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

==同餘關係==
{{About|mod n的表示法|二元的mod運算|模除|section=yes}}

模算數可以在導入[[整數]]的[[同餘關係]]後，通过经典算数的运算法则来推导模运算的运算法则。若有两个正整数<math>a</math>和<math>b</math>，并且二數的差值<math>a-b</math>為<math>n</math>的整數[[倍數]]，我们就可以说<math>a</math>和<math>b</math>在模<math>n</math>下同餘。数学式表达为：<ref>{{cite web |author1=Emanuel Lazar |title=Math 170 lecture notes |url=https://www2.math.upenn.edu/~mlazar/math170/notes06-2.pdf |website=UPenn |accessdate=2021-10-23 |pages=73 |date=April 30, 2016 |archive-date=2021-10-23 |archive-url=https://web.archive.org/web/20211023045743/https://www2.math.upenn.edu/~mlazar/math170/notes06-2.pdf |dead-url=no }}</ref>
:<math>a \equiv b \pmod n\,</math>

例如
:<math>38 \equiv 14 \pmod {12}\,</math>
因為{{nowrap|38 − 14 {{=}} 24}}，是12的倍數。

上述的概念也對負數有效：
:<math> \begin{align}
-8 &\equiv 7 \pmod 5\\
2 &\equiv -3 \pmod 5\\
 -3 &\equiv -8 \pmod 5.
\end{align}</math>

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

:<math>38 \equiv 14 \pmod {12}\,</math>

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

==运算定律==

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

那么我们有以下运算定律：<ref>{{cite book |author1=Sandor Lehoczky |author2=Richard Rusczky |editor=David Patrick |title=the Art of Problem Solving |isbn=0977304566 |pages=44 |edition=7 |language=en| volume=Vol. 1}}</ref>
:<math>a + c \equiv b + c \pmod n</math>
:<math>a - c \equiv b - c \pmod n</math>
:<math>ac \equiv bc \pmod n</math>
:<math>a^c \equiv b^c \pmod n</math>
:<math>a + p \equiv b + q \pmod n</math>
:<math>ap \equiv bq \pmod n</math>

综上所述，我们在模算数里可以使用除[[除法]]以外的任何[[四则运算]]。

==應用==
模算數在[[数论]]、[[群论]]、[[环论]]、[[紐結理論]]、[[抽象代数]]、[[計算機代數]]、[[密码学]]、[[计算机科学]]及[[化學]]中都有使用<ref>{{cite web |author1=Sharky Kesa et al. |title=Modular Arithmetic |url=https://brilliant.org/wiki/modular-arithmetic/ |website=Brillant |accessdate=2021-10-23 |archive-date=2021-10-26 |archive-url=https://web.archive.org/web/20211026104444/https://brilliant.org/wiki/modular-arithmetic/ |dead-url=no }}</ref>，也出現在[[視覺藝術]]及[[音乐]]。

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

模算數也常作為識別碼的[[校验码]]。例如[[国际银行账户号码]]（IBAN）就用模97的餘數來避免輸入編號時的錯誤。

在密碼學中，模算數是 [[RSA加密演算法|RSA]]及[[迪菲-赫爾曼密鑰交換|迪菲-赫爾曼]]等[[公开密钥加密]]系統的基礎，也提到了和 [[椭圆曲线]]有關的[[有限域]]，用在許多的[[对称密钥算法]]中，包括[[高级加密标准]]（AES）、[[國際資料加密演算法]]（IDEA）、及[[RC4]]。RSA和迪菲-赫爾曼密鑰交換用到了[[模冪]]。

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

計算機科學中，模算數會以[[位操作]]的方式表示，也和其他定長度、循環式的[[数据结构]]有關。許多[[编程语言]]及[[计算器]]中都有[[模除]]，而[[逻辑异或|XOR]]是二個位元在模2下的和。

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

音樂上，模12的模算數用在[[十二平均律]]的系統中，其中有[[純八度]]及[[異名同音]]的情形（<!--pitches in a 1∶2 or 2∶1 ratio are equivalent,-->例如[[升音符]]的C音和[[降音符]]的D音會視為是同一個音）。

[[去九法]]是徒手計算時快速的檢查工具，是以模9的模算數為基礎，而且其中最重要的性質是<math>10 \equiv 1 \pmod 9</math>。

模7的模算數在許多計算特定日期是星期幾的[[星期的計算|演算法]]中出現，特別是[[蔡勒公式]]及{{le|判决日法则|doomsday algorithm}}中。

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

==相關條目==
{{Div col||25em}}
* [[布尔环]]
* [[環形緩衝區]]
* [[同餘關係]]
* [[除法]]
* [[有限域]]
* [[勒让德符号]]
* [[模冪]]
* [[模反元素]]
* [[模除]]
* [[数论]]
* [[皮萨诺周期]]（模n下的斐波那契序列）
* [[原根]]
* [[二次互反律]]
* [[二次剩余]]
<!--* [[Rational reconstruction (mathematics)]]
* [[Reduced residue system]]
* [[Serial number arithmetic]] (a special case of modular arithmetic)-->
* [[两元素布尔代数]]
* 和模算數有關的群論主題：
** [[循環群]]
** [[整数模n乘法群]]
* 其他和模算數有關的重要定理：
** [[卡邁克爾函數]]
** [[中国剩余定理]]
** [[欧拉定理 (数论)]]
** [[费马小定理]]
** [[拉格朗日定理 (群論)]]
<!--** [[Thue's lemma]]-->
{{Div col end}}

==參考資料==
{{reflist|2}}

[[Category:同余]]
[[Category:環論]]
[[Category:群论]]