同餘

同餘（英語：Congruence modulo，符號：≡）在數學中是指數論中的一種等價關係。當兩個整數除以同一個正整數，若得相同餘數，則二整數同餘。同餘是抽象代數中的同餘關係的原型。最先引用同餘的概念與「≡」符號者為德國數學家高斯。

同餘符號

兩個整數$a$，$b$，若它們除以正整數$m$所得的餘數相等，則稱$a$，$b$對於模$m$同餘

記作$a\equiv b{\pmod {m}}$

讀作$a$同餘於$b$模$m$，或讀作$a$與$b$關於模$m$同餘。

比如$26\equiv 14{\pmod {12}}$。

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

同餘類

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

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

剩餘系

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

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

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

性質

整除性

$a\equiv b{\pmod {m}}\Rightarrow c\cdot m=a-b,c\in \mathbb {Z}$ （即是說 a 和 b 之差是 m 的倍數）
換句話說，$a\equiv b{\pmod {m}}\Rightarrow m\mid (a-b)$

同餘可以用來檢驗一個數是否可以整除另外一個數，見整除規則。

傳遞性

$\left.{\begin{matrix}a\equiv b{\pmod {m}}\\b\equiv c{\pmod {m}}\end{matrix}}\right\}\Rightarrow a\equiv c{\pmod {m}}$

保持基本運算

$\left.{\begin{matrix}a\equiv b{\pmod {m}}\\c\equiv d{\pmod {m}}\end{matrix}}\right\}\Rightarrow \left\{{\begin{matrix}a\pm c\equiv b\pm d{\pmod {m}}\\ac\equiv bd{\pmod {m}}\end{matrix}}\right.$
當$c=d$時，則為等量加法、減法：$a\pm c\equiv b\pm c{\pmod {m}}$
這性質更可進一步引申成為這樣：
$a\equiv b{\pmod {m}}\Rightarrow {\begin{cases}an\equiv bn{\pmod {m}},\forall n\in \mathbb {Z} \\a^{n}\equiv b^{n}{\pmod {m}},\forall n\in \mathbb {N} ^{*}\\P(a)\equiv P(b){\pmod {m}}\end{cases}}$
其中$P(x)$為任意整係數多項式函數。

放大縮小底數

k為整數，n為正整數，$(km\pm a)^{n}\equiv (\pm a)^{n}{\pmod {m}}$

放大縮小模數

$k$為正整數，$a\equiv b{\pmod {m}}$，若且唯若$ka\equiv kb{\pmod {km}}$

除法原理一

若$ka\equiv kb{\pmod {m}}$且$k,m$互質，則$a\equiv b{\pmod {m}}$

除法原理二

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

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

$m$ 的因數也可以整除 $(a-b)$。亦即，$m$ 是 $n$ 的倍數：$m=c\times n$，$n|m$。因為 $m|(a-b)$，所以 $n|(a-b)\Rightarrow a\equiv b{\pmod {n}}$。

$a\equiv b{\pmod {cn}}\Rightarrow a\equiv b{\pmod {n}}$

$\left.{\begin{matrix}a\equiv b{\pmod {m}}\\n|m\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {n}}$

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

$\left.{\begin{matrix}ac\equiv bc{\pmod {m}}\\(c,m)=1\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {m}}$

如果 $m_{1}|(a-b)$ 而且 $m_{2}|(a-b)$，那麼 $m_{1}$ 與 $m_{2}$ 的最小公倍數必定可以整除 $(a-b)$，記為 $a\equiv b{\pmod {[m_{1},m_{2}]}}$。這可以推廣成以下性質：

$\left.{\begin{matrix}a\equiv b{\pmod {m_{1}}}\\a\equiv b{\pmod {m_{2}}}\\\vdots \\a\equiv b{\pmod {m_{n}}}\\(n\geq 2)\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {[m_{1},m_{2},\cdots ,m_{n}]}}$

上面的最後一個性質可以使用算術基本定理與集合來解釋。一個大於1的正整數 $q$ 可以分解為一串質數冪的乘積：$q=p_{1}^{c_{1}}\times p_{2}^{c_{2}}\times ...\times p_{n}^{c_{n}}$（$p_{i}$ 兩兩相異，且$c_{i}>0$），令 $S_{q}$ 為所有能整除 $q$ 的質數冪的集合，即 $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$ 為正整數，則 $r$ 整除 $q$，當且僅當 $S_{r}$ 是 $S_{q}$ 的子集。令 $m_{1}|q$ 且 $m_{2}|q$，則$S_{m_{1}}$ 與 $S_{m_{2}}$ 的聯集必定也是 $S_{q}$ 的子集。取這個聯集中冪次最高的各個元素，它們的乘積就是 $m_{1}$ 與 $m_{2}$ 的最小公倍數$[m_{1},m_{2}]$。事實上，有 $S_{[m_{1},m_{2}]}=S_{m_{1}}\cup S_{m_{2}}$，所以 $[m_{1},m_{2}]$ 也能夠整除 $q$ 。

同餘關係式

威爾遜定理

主條目：威爾遜定理

$(p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)$

費馬小定理

主條目：費馬小定理

$a^{p}\equiv a{\pmod {p}}$

歐拉定理

主條目：歐拉定理 (數論)

$a^{\varphi (n)}\equiv 1{\pmod {n}}$

卡邁克爾函數

主條目：卡邁克爾函數

$a^{\lambda (n)}\equiv 1{\pmod {n}}$

階乘冪

主條目：階乘冪

$(x)_{k}\equiv x(x-1)(x-2)\cdots (x-k+1)\equiv 0{\pmod {k!}}$

盧卡斯定理

主條目：盧卡斯定理

${\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},$

組合數最小周期

${\binom {m+p^{k+[log_{p}n]}}{n}}\equiv {\binom {m}{n}}{\pmod {p^{k}}}$

設$N=\prod _{i}p_{i}^{k_{i}}$，則${\binom {m+L(n,N)}{n}}\equiv {\binom {m}{n}}{\pmod {N}}$，其中$L(n,N)=\prod _{i}p_{i}^{k_{i}+[log_{p}n]}=N\prod _{i}p_{i}^{[log_{p}n]}$

相關概念

模反元素

主條目：模反元素

$a^{-1}{\dot {a}}\equiv 1{\pmod {n}}$

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

原根

主條目：原根

存在最小的正整數d使得$a^{d}\equiv 1{\pmod {n}}$成立，且$d=\varphi (n)$。

同餘方程

線性同餘方程

主條目：線性同餘方程

$ax\equiv b{\pmod {n}}$

考慮最大公約數，有解時用輾轉相除法等方法求解。

線性同餘方程組

主條目：中國剩餘定理

${\begin{cases}a_{1}x\equiv b_{1}{\pmod {m_{1}}}\\a_{2}x\equiv b_{2}{\pmod {m_{2}}}\\\qquad \qquad \vdots \\a_{n}x\equiv b_{n}{\pmod {m_{n}}}\\\end{cases}}$

先求解每一個線性同餘方程，再用中國剩餘定理解方程組。

二次剩餘

主條目：二次剩餘

$x^{2}\equiv d{\pmod {p}}$

勒讓德符號、雅可比符號、克羅內克符號、二次互反律用於判別d是否為模n的二次剩餘。

高次剩餘

主條目：高次剩餘

$x^{n}\equiv d{\pmod {p}}$

例子

• 求自然數a的個位數字，就是求a與哪一個數對於模10同餘。

• $10\equiv 1({\textrm {mod}}\ 3),10^{n}\equiv 1({\textrm {mod}}\ 3),10001\equiv 10^{4}+1\equiv 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;
}

參見

• 合同_(數學)
• 等價關係
• 模除
• 不定方程