[科普中國]-同余類

數(shù)學(xué)上，同余（英語：congruence modulo，符號(hào)：≡）是數(shù)論中的一種等價(jià)關(guān)系。當(dāng)兩個(gè)整數(shù)除以同一個(gè)正整數(shù)，若得相同余數(shù)，則二整數(shù)同余。同余是抽象代數(shù)中的同余關(guān)系的原型。最先引用同余的概念與“≡”符號(hào)者為德國數(shù)學(xué)家高斯。

由對(duì)于模n同余的所有整數(shù)組成的這個(gè)集合稱為同余類（congruence class或residue class）。

同余符號(hào)兩個(gè)整數(shù)，，若它們除以正整數(shù)所得的余數(shù)相等，則稱，對(duì)于模同余

記作

讀作同余于模，或讀作與關(guān)于模同余。

比如。

同余于的符號(hào)是同余相等符號(hào)≡。統(tǒng)一碼值為 U+2261。但因?yàn)榉奖憷碛?，人們有時(shí)會(huì)把它(誤)寫為普通等號(hào) (=)。1

同余類如同任何同余關(guān)系，對(duì)于模同余是一種等價(jià)關(guān)系，整數(shù)的等價(jià)類是一個(gè)集合，標(biāo)記為。由對(duì)于模同余的所有整數(shù)組成的這個(gè)集合稱為同余類（congruence class或residue class）；假若從上下文知道模，則也可標(biāo)記為。

同余類中的每個(gè)元素都可以拿來代表該同余類，稱為該同余類的代表數(shù)（英語：representative）。2

余數(shù)系統(tǒng)余數(shù)系統(tǒng)（英語：residue system）亦即模n同余類的代表數(shù)的集合，通常使用的代表數(shù)是最小非負(fù)整數(shù)，因?yàn)樗浅ㄖ械膽?yīng)當(dāng)余數(shù)。要注意的是，對(duì)于同一個(gè)模數(shù)n，不同的同余類不等價(jià)，亦即，屬于不同同余類的整數(shù)不同余于模數(shù)n，或者說，模n余數(shù)系統(tǒng)中的任二元素不同余于模n；而且，整數(shù)域中的每個(gè)整數(shù)只屬于模數(shù)n的一個(gè)同余類，因?yàn)槟將整數(shù)域劃分為互斥區(qū)塊，每個(gè)區(qū)塊是一個(gè)同余類。

一個(gè)完整余數(shù)系統(tǒng)（英語：complete residue system）指的是模n的全部同余類的代表數(shù)的集合；因?yàn)橛鄶?shù)系統(tǒng)中的任二元素不同余于模n，所以它也稱為非同余余數(shù)的完整系統(tǒng)（英語：complete system of incongruent residues）。例如，模3有三個(gè)同余類，其完整余數(shù)系統(tǒng)可以是。如果該集合是由每個(gè)同余類的最小非負(fù)整數(shù)所組成，亦即，則稱該集合為模n的最小余數(shù)系統(tǒng)（英語：least residue system）。

模n完整余數(shù)系統(tǒng)中，與模n互質(zhì)的代表數(shù)所構(gòu)成的集合，稱為模n的簡(jiǎn)約余數(shù)系統(tǒng)（英語：reduced residue system），其元素個(gè)數(shù)記為，亦即歐拉函數(shù)。例如，模的簡(jiǎn)約余數(shù)系統(tǒng)為或。如果模n是質(zhì)數(shù)，那么它的最小簡(jiǎn)約余數(shù)系統(tǒng)是，只比最小余數(shù)系統(tǒng)少一個(gè)0。3

性質(zhì)整除性（即是說 a 和 b 之差是 m 的倍數(shù)）
換句話說，

同余可以用來檢驗(yàn)一個(gè)數(shù)是否可以整除另外一個(gè)數(shù)，見整除規(guī)則。

傳遞性

保持基本運(yùn)算這性質(zhì)更可進(jìn)一步引申成為這樣：

除法原理若且互質(zhì)，則

同余關(guān)系式威爾遜定理

費(fèi)馬小定理

歐拉定理

卡邁克爾函數(shù)

階乘冪

應(yīng)用模數(shù)算術(shù)在數(shù)論、群論、環(huán)論、紐結(jié)理論、抽象代數(shù)、計(jì)算機(jī)代數(shù)、密碼學(xué)、計(jì)算機(jī)科學(xué)、化學(xué)、視覺和音樂等學(xué)科中皆有應(yīng)用。

它是數(shù)論的立基點(diǎn)之一，與其各個(gè)面向都相關(guān)。

模數(shù)算術(shù)經(jīng)常被用于計(jì)算標(biāo)識(shí)符中所使用的校驗(yàn)和，比如國際銀行賬戶號(hào)碼（IBANs）就用到了模97的算術(shù)，來捕獲用戶在輸入銀行賬戶號(hào)碼時(shí)的錯(cuò)誤。

于密碼學(xué)中，模數(shù)算術(shù)是RSA與迪菲－赫爾曼密鑰交換等公鑰系統(tǒng)的基礎(chǔ)，它同時(shí)也提供有限域，應(yīng)用于橢圓加密，且用于許多對(duì)稱密鑰加密中，包括高級(jí)加密標(biāo)準(zhǔn)、國際資料加密算法等。

于計(jì)算機(jī)科學(xué), 同余被應(yīng)用于位元運(yùn)算或其他與固定寬度之循環(huán)數(shù)據(jù)結(jié)構(gòu)相關(guān)的操作。

于化學(xué)中,CAS號(hào)（一個(gè)對(duì)各種化合物皆異之的識(shí)別碼）的最后一碼為校驗(yàn)碼，將CAS號(hào)首二部分最后的數(shù)字乘上一，下一碼乘上二，下一碼乘上三以此類推，將所有積加起來再取模10。

在音樂領(lǐng)域，模12用于十二平均律系統(tǒng)。

星期的計(jì)算中取模7算術(shù)極重要。

更廣泛而言，同余在法律、經(jīng)濟(jì)（見賽局理論）或其他社會(huì)科學(xué)領(lǐng)域中也有應(yīng)用。3

本詞條內(nèi)容貢獻(xiàn)者為:

尚華娟 - 副教授 - 上海財(cái)經(jīng)大學(xué)