同餘

稱為模數的元素倍數的不同兩個元素之間的關係
各种各样的
基本

NumberSetinC.svg

延伸
其他

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

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

同余符号编辑

两个整数  ,若它们以正整数 所得的余数相等,则称  对于模 同余

记作 

读作 同余于  ,或读作  关于模 同余。

比如 

同餘於的符號是同餘相等符號。統一碼值為U+2261

同餘類编辑

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

同余類中的每個元素都可以拿來代表該同余類,稱為該同余類的代表數(英語:representative[4]

餘數系統编辑

餘數系統(英語: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的正整數   可以分解為一串質數冪的乘積:   兩兩相異,且 ),令   為所有能整除   的質數冪的集合,即  。設   為正整數,則   整除  ,當且僅當   子集。令   ,則  聯集必定也是   的子集。取這個聯集中冪次最高的各個元素,它們的乘積就是   最小公倍数 。事實上,有  ,所以   也能夠整除  

同余关系式编辑

威尔逊定理编辑

 

费马小定理编辑

 

欧拉定理编辑

 

卡邁克爾函數编辑

 

阶乘幂编辑

 

卢卡斯定理编辑

 

组合数最小周期编辑

 

 ,则 ,其中 [5]

相关概念编辑

模反元素编辑

 

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

原根编辑

存在最小的正整数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. ^ 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). 

参见编辑