同餘

同余（，符號：≡）在数学中是指數論中的一種等價關係。當两个整数除以同一个正整数，若得相同餘數;}-，则二整数同余。同餘是抽象代數中的同餘關係的原型。最先引用同余的概念与「≡」符号者为德國数学家高斯。

定義
對某兩個整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，也就是嚴格來說，存在整數k使得

: a-b = km

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

: a \equiv b \pmod{m}

比如

: 26 - 14 = 12 = 1 \times 12

故可以記為

: 26 \equiv 14 \pmod{12}

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

: b \equiv a \pmod{m}

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

同餘類
可以證明所有对于模m同餘的整數對構成一個（整数系\Z上的）等价关系，換句話說，對於任意兩個整数a，b：

: (1) a \equiv a \pmod{m}
: (2) [a \equiv b \pmod{m}] \Rightarrow [b \equiv a \pmod{m}]
: (3) \big\{[a \equiv b \pmod{m}] \wedge [b \equiv c \pmod{m}]\big\}
\Rightarrow [a \equiv c \pmod{m}]

故以下的集合

: {[a]}_m
:=
\left\{z \in \Z \,\big|\, (\exists k \in \Z)(z = a + km)\right\}
: \;\;\;\;\;\,=\left\{\ldots, a - 2m, a - m, a, a + m, a + 2m, \ldots \right\}

可稱為a对于模m的同余類（或），也可標記為\overline{a}_m；模m在上下文很清楚時，也可簡記為\displaystyle [a]。a會被稱為該同余類的代表數（）。

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

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

模n完全剩餘系中，與模n互質的代表數所構成的集合，稱為模n的簡約剩餘系（），其元素個數記為\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}{{NoteTag|但是，a^n \equiv b^n \pmod{m}不能推論a \equiv b \pmod{m}.}}

其中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 \ge 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-1} \equiv 1 \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 mp2) ? (d m) d -= m;
a

注释
参考文献
参见

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