同餘

同餘在數學中是指數論中的一種等價關係。當兩個整數除以同一個正整數，若得相同餘數，則二整數同餘。同餘是抽象代數中的同餘關係的原型。最先引用同餘的概念與「≡」符號者為德國數學家高斯。同餘符號.兩個整數formula_1，formula_2，若它們除以正整數formula_3所得的餘數相等，則稱formula_1，formula_2對於模formula_3同餘記作formula_7讀作formula_1同餘於formula_2模formula_3，或讀作formula_1與formula_2關於模formula_3同餘。比如formula_14。同餘於的符號是同餘相等符號≡。統一碼值為codice_1。同餘類.如同任何同餘關係，對於模formula_15同餘是一種等價關係，整數formula_1的等價類是一個集合formula_17，標記為formula_18。由對於模formula_15同餘的所有整陣列成的這個集合稱為同餘類；假若從上下文知道模formula_15，則也可標記為formula_21。同餘類中的每個元素都可以拿來代表該同餘類，稱為該同餘類的代表數。剩餘系.剩餘系亦即模formula_15同餘類的代表數的集合，通常使用的代表數是最小非負整數，因為它是除法中的應當餘數。要注意的是，對於同一個模數formula_15，不同的同餘類不等價，亦即，屬於不同同餘類的整數不同餘於模數formula_15，或者說，模formula_15剩餘系中的任二元素不同餘於模formula_15；而且，整數域中的每個整數只屬於模數formula_15的一個同餘類，因為模formula_15將整數域劃分為互斥區塊，每個區塊是一個同餘類。一個完全剩餘系。模formula_15完全剩餘系中，與模formula_15互質的代表數所構成的集合，稱為模formula_15的簡約剩餘系，其元素個數記為formula_39，亦即尤拉函式。例如，模formula_40的簡約剩餘系為formula_41或formula_42。如果模formula_15是質數，那麼它的最小簡約剩餘系是formula_44，只比最小剩餘系少一個formula_45。性質.整除性.formula_46 換句話說，formula_47同餘可以用來檢驗一個數是否可以整除另外一個數，見整除規則。傳遞性.formula_48保持基本運算.formula_49當formula_50時，則為等量加法、減法：formula_51這性質更可進一步引申成為這樣：formula_52放大縮小底數.k為整數，n為正整數，formula_54放大縮小模數.formula_55為正整數，formula_7，若且唯若formula_57除法原理一.若formula_58且formula_59互質，則formula_7除法原理二.每個正整數都可以分解為數個因數的乘積，稱為整數分解。例如 formula_61，因數 formula_31 與 formula_63 都可以整除 formula_64，記為 formula_65 與 formula_66。如果 formula_64 可以整除某正整數 formula_1，亦即 formula_69，那麼 formula_64 就是 formula_1 的因數：formula_72，其中 formula_2 為另一因數。formula_74，因此，formula_64 的因數也可以整除 formula_1：formula_77。formula_7 等價於 formula_79，也就是 formula_80。亦即，如果 formula_80，那麼它可以寫成 formula_7，因此有以下除法原理：formula_3 的因數也可以整除 formula_84。亦即，formula_3 是 formula_15 的倍數：formula_87，formula_88。因為 formula_80，所以 formula_90。formula_91formula_92現假設 formula_3 可以整除 formula_84 的倍數 formula_95。如果 formula_3 和 formula_97 互質，那麼 formula_3 必定可以整除 formula_84：formula_101。formula_102如果 formula_103 而且 formula_104，那麼 formula_105 與 formula_106 的最小公倍數必定可以整除 formula_84，記為 formula_108。這可以推廣成以下性質：formula_109上面的最後一個性質可以使用算術基本定理與集合來解釋。一個大於1的正整數 formula_110 可以分解為一串質數冪的乘積：formula_111，令 formula_114 為所有能整除 formula_110 的質數冪的集合，即 formula_116。設 formula_117 為正整數，則 formula_117 整除 formula_110，當且僅當 formula_120 是 formula_114 的子集。令 formula_122 且 formula_123，則formula_124 與 formula_125 的聯集必定也是 formula_114 的子集。取這個聯集中冪次最高的各個元素，它們的乘積就是 formula_105 與 formula_106 的最小公倍數formula_129。事實上，有 formula_130，所以 formula_129 也能夠整除 formula_110 。同餘關係式.威爾遜定理.formula_133費馬小定理.formula_134尤拉定理.formula_135卡邁克爾函式.formula_136階乘冪.formula_137盧卡斯定理.formula_138組合數最小週期.formula_139設formula_140，則formula_141，其中formula_142相關概念.模反元素.formula_143可用輾轉相除法、尤拉定理、卡邁克爾函式求解。原根.存在最小的正整數d使得formula_144成立，且formula_145。同餘方程.線性同餘方程.formula_146考慮最大公約數，有解時用輾轉相除法等方法求解。線性同餘方程組.formula_147先求解每一個線性同餘方程，再用中國剩餘定理解方程組。二次剩餘.formula_148勒讓德符號、雅可比符號、克羅內克符號、二次互反律用於判別d是否為模n的二次剩餘。高次剩餘.formula_149應用.模數算術在數論、群論、環論、紐結理論、抽象代數、計算機代數、密碼學、電腦科學、化學、視覺和音樂等學科中皆有應用。它是數論的立基點之一，與其各個面向都相關。模數算術經常被用於計算識別符號中所使用的校驗和，比如國際銀行賬戶號碼就用到了模97的算術，來捕獲使用者在輸入銀行帳戶號碼時的錯誤。於密碼學中，模數算術是RSA與迪菲－赫爾曼金鑰交換等公鑰系統的基礎，它同時也提供有限域，應用於 橢圓加密，且用於許多對稱金鑰加密中，包括高階加密標準、國際資料加密演演算法等。於電腦科學, 同餘被應用於位元運算或其他與固定寬度之迴圈資料結構相關的操作。於化學中, CAS號的最後一碼為校驗碼，將CAS號首二部分最後的數字乘上一，下一碼乘上二，下一碼乘上三以此類推，將所有積加起來再取模10。在音樂領域，模12用於十二平均律系統。星期的計算中取模7算術極重要。更廣泛而言，同餘在法律、經濟或其他社會科學領域中也有應用。範例.以下為快速展示小於63位元無號整數之模數乘法的C程式，且轉換過程中不發生溢位。計算 a * b (mod m)之演演算法:uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)uint64_t d = 0, mp2 = m » 1;int i;if (a &gt;= m) a %= m;if (b &gt;= m) b %= m;for (i = 0; i  m) d -= m;a «= 1;return d%m;