跳至內容

同餘

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

同餘(英語: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). 

參見

[編輯]