同餘類

數學上，同餘（英語：congruence modulo，符號：≡）是數論中的一種等價關係。當兩個整數除以同一個正整數，若得相同餘數，則二整數同餘。同餘是抽象代數中的同餘關係的原型。最先引用同餘的概念與“≡”符號者為德國數學家高斯。

由對於模n同餘的所有整數組成的這個集合稱為同餘類（congruence class或residue class）。

基本介紹

• 中文名：同餘類
• 外文名：congruence class或residue class
• 領域：數學

同餘符號

兩個整數，，若它們除以正整數所得的餘數相等，則稱，對於模同餘

記作

讀作同餘於模，或讀作與關於模同餘。

比如。

同餘於的符號是同餘相等符號≡。統一碼值為 U+2261。但因為方便理由，人們有時會把它(誤)寫為普通等號 (=)。

同餘類

如同任何同餘關係，對於模同餘是一種等價關係，整數的等價類是一個集合，標記為。由對於模同餘的所有整數組成的這個集合稱為同餘類（congruence class或residue class）；假若從上下文知道模，則也可標記為。

同餘類中的每個元素都可以拿來代表該同餘類，稱為該同餘類的代表數（英語：representative）。

餘數系統

餘數系統（英語：residue system）亦即模n同餘類的代表數的集合，通常使用的代表數是最小非負整數，因為它是除法中的應當餘數。要注意的是，對於同一個模數n，不同的同餘類不等價，亦即，屬於不同同餘類的整數不同餘於模數n，或者說，模n餘數系統中的任二元素不同餘於模n；而且，整數域中的每個整數隻屬於模數n的一個同餘類，因為模n將整數域劃分為互斥區塊，每個區塊是一個同餘類。

一個完整餘數系統（英語：complete residue system）指的是模n的全部同餘類的代表數的集合；因為餘數系統中的任二元素不同餘於模n，所以它也稱為非同餘餘數的完整系統（英語：complete system of incongruent residues）。例如，模3有三個同餘類，其完整餘數系統可以是。如果該集合是由每個同餘類的最小非負整數所組成，亦即，則稱該集合為模n的最小餘數系統（英語：least residue system）。

模n完整餘數系統中，與模n互質的代表數所構成的集合，稱為模n的簡約餘數系統（英語：reduced residue system），其元素個數記為，亦即歐拉函式。例如，模的簡約餘數系統為或。如果模n是質數，那么它的最小簡約餘數系統是，只比最小餘數系統少一個0。

性質

整除性

（即是說 a 和 b 之差是 m 的倍數）
換句話說，

同餘可以用來檢驗一個數是否可以整除另外一個數，見整除規則。

傳遞性

保持基本運算

這性質更可進一步引申成為這樣：

除法原理

若且互質，則

同餘關係式

威爾遜定理

費馬小定理

歐拉定理

卡麥可函式

階乘冪

套用

模數算術在數論、群論、環論、紐結理論、抽象代數、計算機代數、密碼學、計算機科學、化學、視覺和音樂等學科中皆有套用。

它是數論的立基點之一，與其各個面向都相關。

模數算術經常被用於計算標識符中所使用的校驗和，比如國際銀行賬戶號碼（IBANs）就用到了模97的算術，來捕獲用戶在輸入銀行賬戶號碼時的錯誤。

於密碼學中，模數算術是RSA與迪菲－赫爾曼密鑰交換等公鑰系統的基礎，它同時也提供有限域，套用於橢圓加密，且用於許多對稱密鑰加密中，包括高級加密標準、國際資料加密算法等。

於計算機科學, 同餘被套用於位元運算或其他與固定寬度之循環數據結構相關的操作。

於化學中,CAS號（一個對各種化合物皆異之的識別碼）的最後一碼為校驗碼，將CAS號首二部分最後的數字乘上一，下一碼乘上二，下一碼乘上三以此類推，將所有積加起來再取模10。

在音樂領域，模12用於十二平均律系統。

星期的計算中取模7算術極重要。

更廣泛而言，同餘在法律、經濟（見賽局理論）或其他社會科學領域中也有套用。