同余

同余（英语：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;
}