同餘

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

同余符号

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

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

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

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

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

同餘類

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

注释

参考文献

参见

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