Agfdhyk

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

同余符号

两个整数a{displaystyle a}，b{displaystyle b}，若它们除以正整数m{displaystyle m}所得的余数相等，则称a{displaystyle a}，b{displaystyle b}对于模m{displaystyle m}同余

记作a≡b(modm){displaystyle aequiv b{pmod {m}}}

读作a{displaystyle a}同余于b{displaystyle b}模m{displaystyle m}，或读作a{displaystyle a}与b{displaystyle b}关于模m{displaystyle m}同余。

比如26≡14(mod12){displaystyle 26equiv 14{pmod {12}}}。

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

同餘類

如同任何同餘關係，對於模n{displaystyle n}同餘是一種等價關係，整數a{displaystyle a}的等價類是一個集合{…,a−2n,a−n,a,a+n,a+2n,…}{displaystyle left{ldots ,a-2n,a-n,a,a+n,a+2n,ldots right}}，標記為a¯n{displaystyle {overline {a}}_{n}}。由對於模n{displaystyle n}同餘的所有整數組成的這個集合稱為同餘類（congruence class或residue class）；假若從上下文知道模n{displaystyle n}，則也可標記為[a]{displaystyle displaystyle [a]}。

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

餘數系統

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

一個完整餘數系統（英语：complete residue system）指的是模n{displaystyle n}的全部同餘類的代表數的集合；因為餘數系統中的任二元素不同餘於模n{displaystyle n}，所以它也稱為非同餘餘數的完整系統（英语：complete system of incongruent residues）。例如，模3{displaystyle 3}有三個同餘類[0],[1],[2]{displaystyle [0],[1],[2]}，其完整餘數系統可以是{9,12+1,15+2}{displaystyle {9,12+1,15+2}}。如果該集合是由每個同餘類的最小非負整數所組成，亦即{0,1,2,...,n−1}{displaystyle {0,1,2,...,n-1}}，則稱該集合為模n{displaystyle n}的最小餘數系統（英语：least residue system）。

模n{displaystyle n}完整餘數系統中，與模n{displaystyle n}互質的代表數所構成的集合，稱為模n{displaystyle n}的簡約餘數系統（英语：reduced residue system），其元素個數記為ϕ(n){displaystyle phi (n)}，亦即欧拉函数。例如，模6{displaystyle 6}的簡約餘數系統為{1,5}{displaystyle {1,5}}或{7,11}{displaystyle {7,11}}。如果模n{displaystyle n}是質數，那麼它的最小簡約餘數系統是{1,2,...,n−1}{displaystyle {1,2,...,n-1}}，只比最小餘數系統少一個0{displaystyle 0}。

性质

整除性

a≡b(modm)⇒c⋅m=a−b,c∈Z{displaystyle aequiv b{pmod {m}}Rightarrow ccdot m=a-b,cin mathbb {Z} } （即是說 a 和 b 之差是 m 的倍數）
換句話說，a≡b(modm)⇒m∣(a−b){displaystyle aequiv b{pmod {m}}Rightarrow mmid (a-b)}^{[註 1]}

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

传递性

a≡b(modm)b≡c(modm)}⇒a≡c(modm){displaystyle left.{begin{matrix}aequiv b{pmod {m}}\bequiv c{pmod {m}}end{matrix}}right}Rightarrow aequiv c{pmod {m}}}

保持基本运算

a≡b(modm)c≡d(modm)}⇒{a±c≡b±d(modm)ac≡bd(modm){displaystyle left.{begin{matrix}aequiv b{pmod {m}}\cequiv d{pmod {m}}end{matrix}}right}Rightarrow left{{begin{matrix}apm cequiv bpm d{pmod {m}}\acequiv bd{pmod {m}}end{matrix}}right.}
這性質更可進一步引申成為這樣：
a≡b(modm)⇒{an≡bn(modm),∀n∈Zan≡bn(modm),∀n∈N0{displaystyle aequiv b{pmod {m}}Rightarrow {begin{cases}anequiv bn{pmod {m}},forall nin mathbb {Z} \a^{n}equiv b^{n}{pmod {m}},forall nin mathbb {N} ^{0}end{cases}}}^{[註 2]}

放大縮小底數

k為整數，n為正整數，(km±a)n≡(±a)n(modm){displaystyle (kmpm a)^{n}equiv (pm a)^{n}{pmod {m}}}

放大縮小模數

k{displaystyle k}為正整數，a≡b(modm){displaystyle aequiv b{pmod {m}}}，若且唯若ka≡kb(modkm){displaystyle kaequiv kb{pmod {km}}}

除法原理一

若ka≡kb(modm){displaystyle kaequiv kb{pmod {m}}}且k,m{displaystyle k,m}互質，則a≡b(modm){displaystyle aequiv b{pmod {m}}}

除法原理二

每個正整數都可以分解為數個因數的乘積，稱為整数分解。例如 15=3×5{displaystyle 15=3times 5}，因數 3{displaystyle 3} 與 5{displaystyle 5} 都可以整除 15{displaystyle 15}，記為 3|15{displaystyle 3|15} 與 5|15{displaystyle 5|15}。如果 15{displaystyle 15} 可以整除某正整數 a{displaystyle a}，亦即 15|a{displaystyle 15|a}，那麼 15{displaystyle 15} 就是 a{displaystyle a} 的因數：a=15×b{displaystyle a=15times b}，其中 b{displaystyle b} 為另一因數。a=15×b=(3×5)×b{displaystyle a=15times b=(3times 5)times b}，因此，15{displaystyle 15} 的因數也可以整除 a{displaystyle a}：(3|15)∧(15|a)⇒3|a{displaystyle (3|15)wedge (15|a)Rightarrow 3|a}。

a≡b(modm){displaystyle aequiv b{pmod {m}}} 等價於 (a−b)≡0(modm){displaystyle (a-b)equiv 0{pmod {m}}}，也就是 m|(a−b){displaystyle m|(a-b)}。亦即，如果 m|(a−b){displaystyle m|(a-b)}，那麼它可以寫成 a≡b(modm){displaystyle aequiv b{pmod {m}}}，因此有以下除法原理：

m{displaystyle m} 的因數也可以整除 (a−b){displaystyle (a-b)}。亦即，m{displaystyle m} 是 n{displaystyle n} 的倍數：m=c×n{displaystyle m=ctimes n}，n|m{displaystyle n|m}。因為 m|(a−b){displaystyle m|(a-b)}，所以 n|(a−b)⇒a≡b(modn){displaystyle n|(a-b)Rightarrow aequiv b{pmod {n}}}。

a≡b(modcn)⇒a≡b(modn){displaystyle aequiv b{pmod {cn}}Rightarrow aequiv b{pmod {n}}}

a≡b(modm)n|m}⇒a≡b(modn){displaystyle left.{begin{matrix}aequiv b{pmod {m}}\n|mend{matrix}}right}Rightarrow aequiv b{pmod {n}}}^{[註 1]}

現假設 m{displaystyle m} 可以整除 (a−b){displaystyle (a-b)} 的倍數 c(a−b){displaystyle c(a-b)}。如果 m{displaystyle m} 和 c{displaystyle c} 互質（記為 (m,c)=1{displaystyle (m,c)=1}），那麼 m{displaystyle m} 必定可以整除 (a−b){displaystyle (a-b)}：m|(a−b)⇒a≡b(modm){displaystyle m|(a-b)Rightarrow aequiv b{pmod {m}}}。

ac≡bc(modm)(c,m)=1}⇒a≡b(modm){displaystyle left.{begin{matrix}acequiv bc{pmod {m}}\(c,m)=1end{matrix}}right}Rightarrow aequiv b{pmod {m}}}^{[註 3]}

如果 m1|(a−b){displaystyle m_{1}|(a-b)} 而且 m2|(a−b){displaystyle m_{2}|(a-b)}，那麼 m1{displaystyle m_{1}} 與 m2{displaystyle m_{2}} 的最小公倍数必定可以整除 (a−b){displaystyle (a-b)}，記為 a≡b(mod[m1,m2]){displaystyle aequiv b{pmod {[m_{1},m_{2}]}}}。這可以推廣成以下性質：

a≡b(modm1)a≡b(modm2)⋮a≡b(modmn)(n≥2)}⇒a≡b(mod[m1,m2,⋯,mn]){displaystyle left.{begin{matrix}aequiv b{pmod {m_{1}}}\aequiv b{pmod {m_{2}}}\vdots \aequiv b{pmod {m_{n}}}\(ngeq 2)end{matrix}}right}Rightarrow aequiv b{pmod {[m_{1},m_{2},cdots ,m_{n}]}}}^{[註 4]}

上面的最後一個性質可以使用算术基本定理與集合來解釋。一個大於1的正整數 q{displaystyle q} 可以分解為一串質數冪的乘積：q=p1c1×p2c2×...×pncn{displaystyle q=p_{1}^{c_{1}}times p_{2}^{c_{2}}times ...times p_{n}^{c_{n}}}（pi{displaystyle p_{i}} 兩兩相異，且ci>0{displaystyle c_{i}>0}），令 Sq{displaystyle S_{q}} 為所有能整除 q{displaystyle q} 的質數冪的集合，即 Sq={p1,p12,⋯,p1c1,p2,p22,⋯,p2c2,⋯,pn,pn2,⋯,pncn}{displaystyle S_{q}={p_{1},p_{1}^{2},cdots ,p_{1}^{c_{1}},p_{2},p_{2}^{2},cdots ,p_{2}^{c_{2}},cdots ,p_{n},p_{n}^{2},cdots ,p_{n}^{c_{n}}}}。設 r{displaystyle r} 為正整數，則 r{displaystyle r} 整除 q{displaystyle q}，當且僅當 Sr{displaystyle S_{r}} 是 Sq{displaystyle S_{q}} 的子集。令 m1|q{displaystyle m_{1}|q} 且 m2|q{displaystyle m_{2}|q}，則Sm1{displaystyle S_{m_{1}}} 與 Sm2{displaystyle S_{m_{2}}} 的聯集必定也是 Sq{displaystyle S_{q}} 的子集。取這個聯集中冪次最高的各個元素，它們的乘積就是 m1{displaystyle m_{1}} 與 m2{displaystyle m_{2}} 的最小公倍数[m1,m2]{displaystyle [m_{1},m_{2}]}。事實上，有 S[m1,m2]=Sm1∪Sm2{displaystyle S_{[m_{1},m_{2}]}=S_{m_{1}}cup S_{m_{2}}}，所以 [m1,m2]{displaystyle [m_{1},m_{2}]} 也能夠整除 q{displaystyle q} 。

同余关系式

威尔逊定理

(p−1)! ≡ −1 (mod p){displaystyle (p-1)! equiv -1 ({mbox{mod}} p)}

费马小定理

ap≡a(modp){displaystyle a^{p}equiv a{pmod {p}}}

欧拉定理

aφ(n)≡1(modn){displaystyle a^{varphi (n)}equiv 1{pmod {n}}}

卡邁克爾函數

aλ(n)≡1(modn){displaystyle a^{lambda (n)}equiv 1{pmod {n}}}

阶乘幂

(x)k≡x(x−1)(x−2)⋯(x−k+1)≡0(modk!){displaystyle (x)_{k}equiv x(x-1)(x-2)cdots (x-k+1)equiv 0{pmod {k!}}}

卢卡斯定理

(mn)≡∏i=0k(mini)(modp),{displaystyle {binom {m}{n}}equiv prod _{i=0}^{k}{binom {m_{i}}{n_{i}}}{pmod {p}},}

组合数最小周期

(m+pk+[logpn]n)≡(mn)(modpk){displaystyle {binom {m+p^{k+[log_{p}n]}}{n}}equiv {binom {m}{n}}{pmod {p^{k}}}}

设N=∏ipiki{displaystyle N=prod _{i}p_{i}^{k_{i}}}，则(m+L(n,N)n)≡(mn)(modN){displaystyle {binom {m+L(n,N)}{n}}equiv {binom {m}{n}}{pmod {N}}}，其中L(n,N)=∏ipiki+[logpn]=N∏ipi[logpn]{displaystyle L(n,N)=prod _{i}p_{i}^{k_{i}+[log_{p}n]}=Nprod _{i}p_{i}^{[log_{p}n]}}^[5]

相关概念

模反元素

a−1a˙≡1(modn){displaystyle a^{-1}{dot {a}}equiv 1{pmod {n}}}

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

原根

存在最小的正整数d使得ad≡1(modn){displaystyle a^{d}equiv 1{pmod {n}}}成立，且d=φ(n){displaystyle d=varphi (n)}。

同余方程

线性同余方程

ax≡b(modn){displaystyle axequiv b{pmod {n}}}

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

线性同余方程组

{a1x≡b1(modm1)a2x≡b2(modm2)⋮anx≡bn(modmn){displaystyle {begin{cases}a_{1}xequiv b_{1}{pmod {m_{1}}}\a_{2}xequiv b_{2}{pmod {m_{2}}}\qquad qquad vdots \a_{n}xequiv b_{n}{pmod {m_{n}}}\end{cases}}}

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

二次剩余

x2≡d(modp){displaystyle x^{2}equiv d{pmod {p}}}

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

高次剩餘

xn≡d(modp){displaystyle x^{n}equiv d{pmod {p}}}

例子

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

• 
  10≡1(mod 3),10n≡1(mod 3),10001≡104+1≡1+1(mod 3){displaystyle 10equiv 1({textrm {mod}} 3),10^{n}equiv 1({textrm {mod}} 3),10001equiv 10^{4}+1equiv 1+1({textrm {mod}} 3)}。

應用

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

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

模數算術經常被用於計算標識符中所使用的校验和，比如国际银行账户号码（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;

}

注释

参考文献

参见

• 合同_(數學)


• 等價關係


• 模除


• 不定方程