同馀

同余（英语：Congruence modulo^[1]，符号：≡）在数学中是指数论中的一种等价关系^[2]。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同馀是抽象代数中的同馀关系的原型^[3]。最先引用同余的概念与“≡”符号者为德国数学家高斯。

各种各样的数

基本

$\mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C}$

正数 $\mathbb {R} ^{+}$
自然数 $\mathbb {N}$
正整数 $\mathbb {Z} ^{+}$
小数
 有限小数
 无限小数
 循环小数
 有理数 $\mathbb {Q}$
代数数 $\mathbb {A}$
实数 $\mathbb {R}$
复数 $\mathbb {C}$
高斯整数 $\mathbb {Z} [i]$

负数 $\mathbb {R} ^{-}$
整数 $\mathbb {Z}$
负整数 $\mathbb {Z} ^{-}$
分数
 单位分数
 二进分数
 规矩数
 无理数
 超越数
 虚数 $\mathbb {I}$
二次无理数
 艾森斯坦整数 $\mathbb {Z} [\omega ]$

延伸

二元数
 四元数 $\mathbb {H}$
八元数 $\mathbb {O}$
十六元数 $\mathbb {S}$
超实数 $^{*}\mathbb {R}$
大实数
 上超实数

双曲复数
 双复数
 复四元数
共四元数（英语：Dual quaternion）
超复数
 超数
 超现实数

其他

质数 $\mathbb {P}$
可计算数
 基数
 阿列夫数
 同馀
 整数数列
 公称值

规矩数
 可定义数
 序数
 超限数
 $p$ 进数
 数学常数

圆周率 $\pi =3.14159265$ …
自然对数的底 $e=2.718281828$ …
虚数单位 $i={\sqrt {-{1}}}$
无限大 $\infty$

定义

对某两个整数 $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$ 同馀的整数对构成一个（整数系 $\mathbb {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 \mathbb {Z} \,{\big |}\,(\exists k\in \mathbb {Z} )(z=a+km)\right\}

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

可称为 $a$ 对于模 $m$ 的同余类（congruence class或residue class），也可标记为 ${\overline {a}}_{m}$ ；模 $m$ 在上下文很清楚时，也可简记为 $\displaystyle [a]$ 。 $a$ 会被称为该同余类的代表数（representative）^[4]。

剩馀系

剩馀系^[5]^[6]（英语：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)$ ^{[注 1]}

同余可以用来检验一个数是否可以整除另外一个数，见整除规则。

传递性

$\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}}$ ^{[注 2]}
其中 $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}}$

除法原理二

$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}}

^{[注 1]}

现假设

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}}

^{[注 3]}

如果

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}]}}

^{[注 4]}

上面的最后一个性质可以使用算术基本定理与集合来解释。一个大于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]}$ ^[7]

同余方程

线性同余方程

$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;
}

注释

^ ^1.0 ^1.1 $m\mid x$ 表示 m 能整除 x，或者说 x 能被 m 整除。
^ 但是， $a^{n}\equiv b^{n}{\pmod {m}}$ 不能推论 $a\equiv b{\pmod {m}}$ .
^ $(m_{1},m_{2},\cdots ,m_{n})$ 表示 $m_{1},m_{2},\cdots ,m_{n}$ 的最大公约数。
^ $[m_{1},m_{2},\cdots ,m_{n}]$ 表示 $m_{1},m_{2},\cdots ,m_{n}$ 的最小公倍数。

参考文献

^ Khan Academy > Congruence Modulo. [2014-10-21]. （原始内容存档于2020-11-04）.
^ Abstract algebra, I. H. Sheth, p.57. [2014-10-21]. （原始内容存档于2014-10-21）.
^ e-Study Guide for: Handbook of Mathematics: Mathematics, Mathematics, p.174. [2014-10-21]. （原始内容存档于2014-10-21）.
^ A Computational Introduction to Number Theory and Algebra, Victor Shoup, p.25. [2014-11-05]. （原始内容存档于2014-11-05）.
^ 国家教育研究院. 完全剩餘系 complete system of residues. 双语词汇、学术名词暨辞书资讯网. [2022-05-21]. （原始内容存档于2022-05-21）.
^ 张鸿林; 葛显良 (编). 英汉数学词汇. 清华大学出版社. 2005: 119, 617.
^ Chi-Jen Lu; Shi-Chun Tsaiy. The Periodic Property of Binomial Coefficients Modulo m and Its Applications. 10th SIAM Conference on Discrete Mathematics. 2000 [2018-09-13]. （原始内容存档于2018-09-14）.

参见

[div-7] 1.0 ^1.1 $m\mid x$ 表示 m 能整除 x，或者说 x 能被 m 整除。

[8] 但是， $a^{n}\equiv b^{n}{\pmod {m}}$ 不能推论 $a\equiv b{\pmod {m}}$ .

[9] $(m_{1},m_{2},\cdots ,m_{n})$ 表示 $m_{1},m_{2},\cdots ,m_{n}$ 的最大公约数。

[10] $[m_{1},m_{2},\cdots ,m_{n}]$ 表示 $m_{1},m_{2},\cdots ,m_{n}$ 的最小公倍数。

[1] Khan Academy > Congruence Modulo. [2014-10-21]. （原始内容存档于2020-11-04）.

[2] Abstract algebra, I. H. Sheth, p.57. [2014-10-21]. （原始内容存档于2014-10-21）.

[3] -Study Guide for: Handbook of Mathematics: Mathematics, Mathematics, p.174. [2014-10-21]. （原始内容存档于2014-10-21）.

[4] A Computational Introduction to Number Theory and Algebra, Victor Shoup, p.25. [2014-11-05]. （原始内容存档于2014-11-05）.

[5] 国家教育研究院. 完全剩餘系 complete system of residues. 双语词汇、学术名词暨辞书资讯网. [2022-05-21]. （原始内容存档于2022-05-21）.

[6] 张鸿林; 葛显良 (编). 英汉数学词汇. 清华大学出版社. 2005: 119, 617.

[11] Chi-Jen Lu; Shi-Chun Tsaiy. The Periodic Property of Binomial Coefficients Modulo m and Its Applications. 10th SIAM Conference on Discrete Mathematics. 2000 [2018-09-13]. （原始内容存档于2018-09-14）.

[1]

[2]

[3]

[4]

[5]

[6]

[注 1]

[注 2]

[注 3]

[注 4]

[7]

同馀

定义

同馀类

剩馀系

性质

整除性

传递性