同餘

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

各式各樣的數

基本

${\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} }$ 正數 ${\displaystyle \mathbb {R} ^{+}}$ 自然數 ${\displaystyle \mathbb {N} }$ 正整數 ${\displaystyle \mathbb {Z} ^{+}}$ 小數 有限小數 無限小數 循環小數 有理數 ${\displaystyle \mathbb {Q} }$ 代數數 ${\displaystyle \mathbb {A} }$ 實數 ${\displaystyle \mathbb {R} }$ 複數 ${\displaystyle \mathbb {C} }$ 高斯整數 ${\displaystyle \mathbb {Z} [i]}$ 負數 ${\displaystyle \mathbb {R} ^{-}}$ 整數 ${\displaystyle \mathbb {Z} }$ 負整數 ${\displaystyle \mathbb {Z} ^{-}}$ 分數 單位分數 二進分數 規矩數 無理數 超越數 虛數 ${\displaystyle \mathbb {I} }$ 二次無理數 艾森斯坦整數 ${\displaystyle \mathbb {Z} [\omega ]}$

延伸

二元數 四元數 ${\displaystyle \mathbb {H} }$ 八元數 ${\displaystyle \mathbb {O} }$ 十六元數 ${\displaystyle \mathbb {S} }$ 超實數 ${\displaystyle ^{*}\mathbb {R} }$ 大實數 上超實數 雙曲複數 雙複數 複四元數 共四元數（英語：Dual quaternion） 超複數 超數 超現實數

其他

質數 ${\displaystyle \mathbb {P} }$ 可計算數 基數 阿列夫數 同餘 整數數列 公稱值 規矩數 可定義數 序數 超限數 p進數 數學常數 圓周率 ${\displaystyle \pi =3.14159265}$… 自然對數的底 ${\displaystyle e=2.718281828}$… 虛數單位 ${\displaystyle i={\sqrt {-{1}}}}$ 無限大 ${\displaystyle \infty }$

閱 論 編

定義

對某兩個整數${\displaystyle a}$，${\displaystyle b}$，若它們除以正整數${\displaystyle m}$所得的餘數相等，則稱${\displaystyle a}$，${\displaystyle b}$對於模${\displaystyle m}$同餘，也就是嚴格來說，存在整數${\displaystyle k}$使得

${\displaystyle a-b=km}$

則稱${\displaystyle a,\,b}$對於除數${\displaystyle m}$是同餘的。一般記做

${\displaystyle a\equiv b{\pmod {m}}}$

比如

${\displaystyle 26-14=12=1\times 12}$

故可以記為

${\displaystyle 26\equiv 14{\pmod {12}}}$

但另一方面，從${\displaystyle a-b=km}$有${\displaystyle b-a=(-k)\times m}$，故${\displaystyle a\equiv b{\pmod {m}}}$等價於

${\displaystyle b\equiv a{\pmod {m}}}$

同餘符號「≡」其UTF-8碼為U+2261。

同餘類

可以證明所有對於模${\displaystyle m}$同餘的整數對構成一個（整數系${\displaystyle \mathbb {Z} }$上的）等價關係，換句話說，對於任意兩個整數${\displaystyle a}$，${\displaystyle b}$：

(1) ${\displaystyle a\equiv a{\pmod {m}}}$

(2) ${\displaystyle [a\equiv b{\pmod {m}}]\Rightarrow [b\equiv a{\pmod {m}}]}$

(3) ${\displaystyle {\big \{}[a\equiv b{\pmod {m}}]\wedge [b\equiv c{\pmod {m}}]{\big \}}\Rightarrow [a\equiv c{\pmod {m}}]}$

故以下的集合

${\displaystyle {[a]}_{m}:=\left\{z\in \mathbb {Z} \,{\big |}\,(\exists k\in \mathbb {Z} )(z=a+km)\right\}}$

${\displaystyle \;\;\;\;\;\,=\left\{\ldots ,a-2m,a-m,a,a+m,a+2m,\ldots \right\}}$

可稱為${\displaystyle a}$對於模${\displaystyle m}$的同餘類（congruence class或residue class），也可標記為${\displaystyle {\overline {a}}_{m}}$；模${\displaystyle m}$在上下文很清楚時，也可簡記為${\displaystyle \displaystyle [a]}$。${\displaystyle a}$會被稱為該同餘類的代表數（representative）^[4]。

剩餘系

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

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

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

性質

整除性

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

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

遞移性

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

保持基本運算

${\displaystyle \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.}$
當${\displaystyle c=d}$時，則為等量加法、減法：${\displaystyle a\pm c\equiv b\pm c{\pmod {m}}}$
這性質更可進一步引申成為這樣：
${\displaystyle 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}}}$^{[註 2]}
其中${\displaystyle P(x)}$為任意整係數多項式函數。

放大縮小底數

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

放大縮小模數

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

除法原理一

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

除法原理二

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

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

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

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

${\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\n|m\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {n}}}$^{[註 1]}

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

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

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

${\displaystyle \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}]}}}$^{[註 4]}

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

同餘關係式

威爾遜定理

主條目：威爾遜定理

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

費馬小定理

主條目：費馬小定理

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$

歐拉定理

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

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

卡邁克爾函數

主條目：卡邁克爾函數

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

階乘冪

主條目：階乘冪

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

盧卡斯定理

主條目：盧卡斯定理

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

組合數最小週期

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

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

相關概念

模反元素

主條目：模反元素

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

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

原根

主條目：原根

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

同餘方程式

線性同餘方程式

主條目：線性同餘方程式

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

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

線性同餘方程組

主條目：中國剩餘定理

${\displaystyle {\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}}}$

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

二次剩餘

主條目：二次剩餘

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

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

高次剩餘

主條目：高次剩餘

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

例子

• 求自然數a的個位數字，就是求a與哪一個數對於模10同餘。
• ${\displaystyle 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;
}