同餘

稱為模數的元素倍數的不同兩個元素之間的關係

同余(英語:Congruence modulo[1]符號:≡)在数学中是指數論中的一種等價關係[2]。當两个整数以同一个正整数,若得相同余数,则二整数同余。同餘是抽象代數中的同餘關係的原型[3]。最先引用同余的概念与「≡」符号者为德國数学家高斯

各种各样的
基本

延伸
其他

圓周率
自然對數的底
虛數單位
無限大

定義

對某兩個整数  ,若它们以正整数 所得的余数相等,则称  对于模 同余,也就是嚴格來說,存在整數 使得

 

則稱 對於除數 同餘的。一般記做

 

比如

 

故可以記為

 

但另一方面,從  ,故 等價於

 

同餘符號「」其UTF-8碼為U+2261

同餘類

可以證明所有对于模 同餘的整數對構成一個(整数 上的)等价关系,換句話說,對於任意兩個整数  

(1)  
(2)  
(3)  

故以下的集合

 
 

可稱為 对于模 同余類congruence classresidue class),也可標記為 ;模 在上下文很清楚時,也可簡記為  會被稱為該同余類的代表數representative[4]

剩餘系

剩餘系[5][6](英語:residue system)亦即模 同餘類的代表數的集合,通常使用的代表數是最小非負整數,因為它是除法中的應當餘數。要注意的是,對於同一個模數 ,不同的同餘類不等價,亦即,屬於不同同餘類的整數不同餘於模數 ,或者說,模 剩餘系中的任二元素不同餘於模 ;而且,整數域中的每個整數只屬於模數 的一個同餘類,因為模 將整數域划分為互斥區塊,每個區塊是一個同餘類。

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

 完全剩餘系中,與模 互質的代表數所構成的集合,稱為模 簡約剩餘系(英語:reduced residue system),其元素個數記為 ,亦即欧拉函数。例如,模 的簡約剩餘系為  。如果模 質數,那麼它的最小簡約剩餘系是 ,只比最小剩餘系少一個 

性质

整除性

  (即是說 a 和 b 之差是 m 的倍數)
換句話說, [註 1]

同余可以用来检验一个数是否可以整除另外一个数,见整除规则

传递性

 

保持基本运算

 
 時,則為等量加法、減法: 
這性質更可進一步引申成為這樣:
 [註 2]
其中 为任意整系数多项式函数。

放大縮小底數

k為整數,n為正整數, 

放大縮小模數

 為正整數, 若且唯若 

除法原理一

  互質,則 

除法原理二

每個正整數都可以分解為數個因數的乘積,稱為整数分解。例如  ,因數    都可以整除  ,記為   。如果   可以整除某正整數  ,亦即  ,那麼   就是   的因數: ,其中   為另一因數。 ,因此,  的因數也可以整除   

  等價於  ,也就是  。亦即,如果  ,那麼它可以寫成  ,因此有以下除法原理:

  的因數也可以整除  。亦即,  倍數  。因為  ,所以  
 
 [註 1]
現假設   可以整除   的倍數  。如果    互質(記為  ),那麼   必定可以整除   
 [註 3]
如果   而且  ,那麼   最小公倍数必定可以整除  ,記為  。這可以推廣成以下性質:
 [註 4]
上面的最後一個性質可以使用算术基本定理集合來解釋。一個大於1的正整數   可以分解為一串質數冪的乘積:   兩兩相異,且 ),令   為所有能整除   的質數冪的集合,即  。設   為正整數,則   整除  ,當且僅當   子集。令   ,則  聯集必定也是   的子集。取這個聯集中冪次最高的各個元素,它們的乘積就是   最小公倍数 。事實上,有  ,所以   也能夠整除  

同余关系式

威尔逊定理

 

费马小定理

 

欧拉定理

 

卡邁克爾函數

 

阶乘幂

 

卢卡斯定理

 

组合数最小周期

 

 ,则 ,其中 [7]

相关概念

模反元素

 

可用輾轉相除法歐拉定理卡邁克爾函數求解。

原根

存在最小的正整数d使得 成立,且 

同余方程

线性同余方程

 

考虑最大公约数,有解时用輾轉相除法等方法求解。

线性同余方程组

 

先求解每一个线性同余方程,再用中国剩余定理解方程组。

二次剩余

 

勒让德符号雅可比符号克罗内克符号二次互反律用于判别d是否为模n的二次剩余。

高次剩餘

 

例子

  • 自然数a的个位数字,就是求a与哪一个数对于模10同余。
  •  

應用

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

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

模數算術經常被用於計算標識符中所使用的校验和,比如国际银行账户号码(IBANs)就用到了模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 >= m) a %= m;
   if (b >= m) b %= m;
   for (i = 0; i < 64; ++i)
   {
       d = (d > mp2) ? (d << 1) - m : d << 1;
       if (a & 0x8000000000000000ULL)
           d += b;
       if (d > m) d -= m;
       a <<= 1;
   }
   return d%m;
}


注释

  1. ^ 1.0 1.1   表示 m 能整除 x,或者说 x 能被 m 整除。
  2. ^ 但是, 不能推論 .
  3. ^  表示 最大公约数
  4. ^  表示 最小公倍数

参考文献

  1. ^ Khan Academy > Congruence Modulo. [2014-10-21]. (原始内容存档于2020-11-04). 
  2. ^ Abstract algebra, I. H. Sheth, p.57. [2014-10-21]. (原始内容存档于2014-10-21). 
  3. ^ e-Study Guide for: Handbook of Mathematics: Mathematics, Mathematics, p.174. [2014-10-21]. (原始内容存档于2014-10-21). 
  4. ^ A Computational Introduction to Number Theory and Algebra, Victor Shoup, p.25. [2014-11-05]. (原始内容存档于2014-11-05). 
  5. ^ 國家教育研究院. 完全剩餘系 complete system of residues. 雙語詞彙、學術名詞暨辭書資訊網. [2022-05-21]. (原始内容存档于2022-05-21). 
  6. ^ 张鸿林; 葛显良 (编). 英汉数学词汇. 清华大学出版社. 2005: 119, 617. 
  7. ^ Chi-Jen Lu; Shi-Chun Tsaiy. The Periodic Property of Binomial Coefficients Modulo m and Its Applications. 10th SIAM Conference on Discrete Mathematics. 2000 [2018-09-13]. (原始内容存档于2018-09-14). 

参见