模算數
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Clock_group.svg/250px-Clock_group.svg.png)
模算數或稱同餘運算(英語:Modular arithmetic)是一個整數的算術系統,其中數字超過一定值後(稱為模或餘數)後會「捲回」到較小的數值,模算數最早是出現在卡爾·弗里德里希·高斯在1801年出版的《算術研究》一書中。
模算數常見的應用是在十二小時制,將一天分為二個以十二小時計算的單位。假設現在七點,八小時後會是三點。用一般的算術加法,會得到7 + 8 = 15,但在十二小時制中,超過十二小時會歸零,不存在「十五點」。類似的情形,若時鐘目前是十二時,二十一小時後會是九點,而不是三十三點。小時數超過十二後會再回到一,為模12的模算數系統。依照上述的定義,12和12本身同餘,也和0同餘,因此12:00的時間也可以稱為是0:00,因為模12時,12和0同餘。
同餘關係
模算數可以在導入整數的同餘關係後,通過經典算數的運算法則來推導模運算的運算法則。若有兩個正整數和,並且二數的差值為的整數倍數,我們就可以說和在模下同餘。數學式表達為:[1]
例如
因為38 − 14 = 24,是12的倍數。
上述的概念也對負數有效:
而同餘關係也可以用計算帶餘除法中的餘數來理解。若正整數和在除以後的餘數相同,。例如:
因為38和14除以12時,餘數都為2。這是因為38 − 14 = 24是12的整數倍。
運算定律
如果,,為任何正整數,
那麼我們有以下運算定律:[2]
應用
模算數在數論、群論、環論、紐結理論、抽象代數、計算機代數、密碼學、計算機科學及化學中都有使用[3],也出現在視覺藝術及音樂。
模算數是數論的基礎之一,也提供了群論、環論及抽象代數中一些重要的範例。
模算數也常作為識別碼的校驗碼。例如國際銀行賬戶號碼(IBAN)就用模97的餘數來避免輸入編號時的錯誤。
在密碼學中,模算數是 RSA及迪菲-赫爾曼等公開密鑰加密系統的基礎,也提到了和 橢圓曲線有關的有限域,用在許多的對稱密鑰算法中,包括高級加密標準(AES)、國際資料加密演算法(IDEA)、及RC4。RSA和迪菲-赫爾曼密鑰交換用到了模冪。
在電腦代數中,模算數常用來限制中間計算的整數系數大小,也限制計算中用到的資料。模算數用在多項式分解中(其中所有已知有效率的演算法都用到了模算數),而針對整數及有理數的多項式最大公因式、線性代數及Gröbner基,最有效率解法都用到了模算數。
計算機科學中,模算數會以位操作的方式表示,也和其他定長度、循環式的數據結構有關。許多程式語言及計算器中都有模除,而XOR是二個位元在模2下的和。
化學中,表示化合物編號的CAS號,最後一碼是校驗碼,是將CAS號前二位數乘以1、下一位乘以2,再下一位乘以3……,最後對10取餘數而得。
音樂上,模12的模算數用在十二平均律的系統中,其中有純八度及異名同音的情形(例如升音符的C音和降音符的D音會視為是同一個音)。
去九法是徒手計算時快速的檢查工具,是以模9的模算數為基礎,而且其中最重要的性質是。
模7的模算數在許多計算特定日期是星期幾的演算法中出現,特別是蔡勒公式及判決日法則中。
模算數也用在像法律(像分配 (政治))、經濟學(像博弈論),若一些社會科學的分析會強調資源的比例分割及分配,也會用到模算數。
參考資料
- ^ 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).