njtynhj

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

同余符号

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

记作a≡b(modm)displaystyle aequiv bpmod m

读作adisplaystyle a同余于bdisplaystyle b模mdisplaystyle m，或读作adisplaystyle a与bdisplaystyle b关于模mdisplaystyle m同余。

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

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

同餘類

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

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

餘數系統

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

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

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

性质

整除性

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

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

传递性

a≡b(modm)b≡c(modm)}⇒a≡c(modm)displaystyle left.beginmatrixaequiv bpmod m\bequiv cpmod mendmatrixrightRightarrow aequiv cpmod m}

保持基本运算

a≡b(modm)c≡d(modm)}⇒a±c≡b±d(modm)ac≡bd(modm)displaystyle left.beginmatrixaequiv bpmod m\cequiv dpmod mendmatrixrightRightarrow leftbeginmatrixapm cequiv bpm dpmod m\acequiv bdpmod mendmatrixright.
這性質更可進一步引申成為這樣：
a≡b(modm)⇒(a−b)displaystyle m^{[註 1]}

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

ac≡bc(modm)(c,m)=1}⇒a≡b(modm)displaystyle left.beginmatrixacequiv bcpmod m\(c,m)=1endmatrixrightRightarrow aequiv bpmod m}^{[註 3]}

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

a≡b(modm1)a≡b(modm2)⋮a≡b(modmn)(n≥2)}⇒a≡b(mod[m1,m2,⋯,mn])displaystyle left.beginmatrixaequiv bpmod m_1\aequiv bpmod m_2\vdots \aequiv bpmod m_n\(ngeq 2)endmatrixrightRightarrow aequiv bpmod [m_1,m_2,cdots ,m_n]}^{[註 4]}

上面的最後一個性質可以使用算术基本定理與集合來解釋。一個大於1的正整數 qdisplaystyle q 可以分解為一串質數冪的乘積：q=p1c1×p2c2×...×pncndisplaystyle q=p_1^c_1times p_2^c_2times ...times p_n^c_n（pidisplaystyle p_i 兩兩相異，且ci>0displaystyle c_i>0），令 Sqdisplaystyle S_q 為所有能整除 qdisplaystyle q 的質數冪的集合，即 Sq=p1,p12,⋯,p1c1,p2,p22,⋯,p2c2,⋯,pn,pn2,⋯,pncndisplaystyle 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。設 rdisplaystyle r 為正整數，則 rdisplaystyle r 整除 qdisplaystyle q，當且僅當 Srdisplaystyle S_r 是 Sqdisplaystyle S_q 的子集。令 m1|qq 且 m2|qq，則Sm1displaystyle S_m_1 與 Sm2displaystyle S_m_2 的聯集必定也是 Sqdisplaystyle S_q 的子集。取這個聯集中冪次最高的各個元素，它們的乘積就是 m1displaystyle m_1 與 m2displaystyle m_2 的最小公倍数[m1,m2]displaystyle [m_1,m_2]。事實上，有 S[m1,m2]=Sm1∪Sm2displaystyle S_[m_1,m_2]=S_m_1cup S_m_2，所以 [m1,m2]displaystyle [m_1,m_2] 也能夠整除 qdisplaystyle q 。

同余关系式

威尔逊定理

(p−1)! ≡ −1 (mod p)displaystyle (p-1)! equiv -1 (mboxmod p)

费马小定理

ap≡a(modp)displaystyle a^pequiv apmod p

欧拉定理

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

卡邁克爾函數

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

阶乘幂

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

卢卡斯定理

(mn)≡∏i=0k(mini)(modp),displaystyle binom mnequiv prod _i=0^kbinom m_in_ipmod p,

组合数最小周期

(m+pk+[logpn]n)≡(mn)(modpk)displaystyle binom m+p^k+[log_pn]nequiv binom mnpmod p^k

设N=∏ipikidisplaystyle N=prod _ip_i^k_i，则(m+L(n,N)n)≡(mn)(modN)displaystyle binom m+L(n,N)nequiv binom mnpmod N，其中L(n,N)=∏ipiki+[logpn]=N∏ipi[logpn]displaystyle L(n,N)=prod _ip_i^k_i+[log_pn]=Nprod _ip_i^[log_pn]^[5]

相关概念

模反元素

a−1a˙≡1(modn)displaystyle a^-1dot aequiv 1pmod n

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

原根

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

同余方程

线性同余方程

ax≡b(modn)displaystyle axequiv bpmod n

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

线性同余方程组

{a1x≡b1(modm1)a2x≡b2(modm2)⋮anx≡bn(modmn)displaystyle begincasesa_1xequiv b_1pmod m_1\a_2xequiv b_2pmod m_2\qquad qquad vdots \a_nxequiv b_npmod m_n\endcases

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

二次剩余

x2≡d(modp)displaystyle x^2equiv dpmod p

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

高次剩餘

xn≡d(modp)displaystyle x^nequiv dpmod 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^nequiv 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;

注释

参考文献

参见

• 合同_(數學)


• 等價關係


• 模除


• 不定方程