同余 （英语：Congruence modulo [ 1] 符号 ：≡）在数学 中是指数论 中的一种等价关系 [ 2] 整数 除 以同一个正整数 ，若得相同余数 ，则二整数同余 。同余是抽象代数 中的同余关系 的原型[ 3] 概念 与“≡”符号 者为德国 数学家 高斯 。
对某两个整数
a
{\displaystyle a}
b
{\displaystyle b}
除 以正整数
m
{\displaystyle m}
a
{\displaystyle a}
b
{\displaystyle b}
m
{\displaystyle m}
k
{\displaystyle k}
a
−
b
=
k
m
{\displaystyle a-b=km}
则称
a
,
b
{\displaystyle a,\,b}
m
{\displaystyle m}
同余的 。一般记做
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
比如
26
−
14
=
12
=
1
×
12
{\displaystyle 26-14=12=1\times 12}
故可以记为
26
≡
14
(
mod
12
)
{\displaystyle 26\equiv 14{\pmod {12}}}
但另一方面，从
a
−
b
=
k
m
{\displaystyle a-b=km}
b
−
a
=
(
−
k
)
×
m
{\displaystyle b-a=(-k)\times m}
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
b
≡
a
(
mod
m
)
{\displaystyle b\equiv a{\pmod {m}}}
同余 符号“≡ ”其UTF-8 码为U+2261。
可以证明所有对于模
m
{\displaystyle m}
整数 系
Z
{\displaystyle \mathbb {Z} }
等价关系 ，换句话说，对于任意两个整数
a
{\displaystyle a}
b
{\displaystyle b}
(1)
a
≡
a
(
mod
m
)
{\displaystyle a\equiv a{\pmod {m}}}
(2)
[
a
≡
b
(
mod
m
)
]
⇒
[
b
≡
a
(
mod
m
)
]
{\displaystyle [a\equiv b{\pmod {m}}]\Rightarrow [b\equiv a{\pmod {m}}]}
(3)
{
[
a
≡
b
(
mod
m
)
]
∧
[
b
≡
c
(
mod
m
)
]
}
⇒
[
a
≡
c
(
mod
m
)
]
{\displaystyle {\big \{}[a\equiv b{\pmod {m}}]\wedge [b\equiv c{\pmod {m}}]{\big \}}\Rightarrow [a\equiv c{\pmod {m}}]}
故以下的集合
[
a
]
m
:=
{
z
∈
Z
|
(
∃
k
∈
Z
)
(
z
=
a
+
k
m
)
}
{\displaystyle {[a]}_{m}:=\left\{z\in \mathbb {Z} \,{\big |}\,(\exists k\in \mathbb {Z} )(z=a+km)\right\}}
=
{
…
,
a
−
2
m
,
a
−
m
,
a
,
a
+
m
,
a
+
2
m
,
…
}
{\displaystyle \;\;\;\;\;\,=\left\{\ldots ,a-2m,a-m,a,a+m,a+2m,\ldots \right\}}
可称为
a
{\displaystyle a}
m
{\displaystyle m}
同余类 （congruence class 或residue class ），也可标记为
a
¯
m
{\displaystyle {\overline {a}}_{m}}
m
{\displaystyle m}
[
a
]
{\displaystyle \displaystyle [a]}
a
{\displaystyle a}
代表数 （representative ）[ 4]
剩余系 [ 5] [ 6] residue system ）亦即模
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
划分 为互斥区块，每个区块是一个同余类。
一个完全剩余系 （英语：complete residue system ）指的是模
n
{\displaystyle n}
n
{\displaystyle n}
非同余余数的完整系统 （英语：complete system of incongruent residues ）。例如，模
3
{\displaystyle 3}
[
0
]
,
[
1
]
,
[
2
]
{\displaystyle [0],[1],[2]}
{
9
,
12
+
1
,
15
+
2
}
{\displaystyle \{9,12+1,15+2\}}
{
0
,
1
,
2
,
.
.
.
,
n
−
1
}
{\displaystyle \{0,1,2,...,n-1\}}
n
{\displaystyle n}
最小剩余系 （英语：least residue system ）。
模
n
{\displaystyle n}
n
{\displaystyle n}
n
{\displaystyle n}
简约剩余系 （英语：reduced residue system ），其元素个数记为
ϕ
(
n
)
{\displaystyle \phi (n)}
欧拉函数 。例如，模
6
{\displaystyle 6}
{
1
,
5
}
{\displaystyle \{1,5\}}
{
7
,
11
}
{\displaystyle \{7,11\}}
n
{\displaystyle n}
素数 ，那么它的最小简约剩余系是
{
1
,
2
,
.
.
.
,
n
−
1
}
{\displaystyle \{1,2,...,n-1\}}
0
{\displaystyle 0}
a
≡
b
(
mod
m
)
⇒
c
⋅
m
=
a
−
b
,
c
∈
Z
{\displaystyle a\equiv b{\pmod {m}}\Rightarrow c\cdot m=a-b,c\in \mathbb {Z} }
a
≡
b
(
mod
m
)
⇒
m
∣
(
a
−
b
)
{\displaystyle a\equiv b{\pmod {m}}\Rightarrow m\mid (a-b)}
[ 注 1]
同余可以用来检验一个数是否可以整除 另外一个数，见整除规则 。
a
≡
b
(
mod
m
)
b
≡
c
(
mod
m
)
}
⇒
a
≡
c
(
mod
m
)
{\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\b\equiv c{\pmod {m}}\end{matrix}}\right\}\Rightarrow a\equiv c{\pmod {m}}}
a
≡
b
(
mod
m
)
c
≡
d
(
mod
m
)
}
⇒
{
a
±
c
≡
b
±
d
(
mod
m
)
a
c
≡
b
d
(
mod
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.}
c
=
d
{\displaystyle c=d}
a
±
c
≡
b
±
c
(
mod
m
)
{\displaystyle a\pm c\equiv b\pm c{\pmod {m}}}
a
≡
b
(
mod
m
)
⇒
{
a
n
≡
b
n
(
mod
m
)
,
∀
n
∈
Z
a
n
≡
b
n
(
mod
m
)
,
∀
n
∈
N
∗
P
(
a
)
≡
P
(
b
)
(
mod
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]
P
(
x
)
{\displaystyle P(x)}
k为整数，n为正整数，
(
k
m
±
a
)
n
≡
(
±
a
)
n
(
mod
m
)
{\displaystyle (km\pm a)^{n}\equiv (\pm a)^{n}{\pmod {m}}}
k
{\displaystyle k}
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
当且仅当
k
a
≡
k
b
(
mod
k
m
)
{\displaystyle ka\equiv kb{\pmod {km}}}
若
k
a
≡
k
b
(
mod
m
)
{\displaystyle ka\equiv kb{\pmod {m}}}
k
,
m
{\displaystyle k,m}
互素 ，则
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
每个正整数都可以分解为数个约数 的乘积，称为整数分解 。例如
15
=
3
×
5
{\displaystyle 15=3\times 5}
3
{\displaystyle 3}
5
{\displaystyle 5}
15
{\displaystyle 15}
3
|
15
{\displaystyle 3|15}
5
|
15
{\displaystyle 5|15}
15
{\displaystyle 15}
a
{\displaystyle a}
15
|
a
{\displaystyle 15|a}
15
{\displaystyle 15}
a
{\displaystyle a}
a
=
15
×
b
{\displaystyle a=15\times b}
b
{\displaystyle b}
a
=
15
×
b
=
(
3
×
5
)
×
b
{\displaystyle a=15\times b=(3\times 5)\times b}
15
{\displaystyle 15}
a
{\displaystyle a}
(
3
|
15
)
∧
(
15
|
a
)
⇒
3
|
a
{\displaystyle (3|15)\wedge (15|a)\Rightarrow 3|a}
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
(
a
−
b
)
≡
0
(
mod
m
)
{\displaystyle (a-b)\equiv 0{\pmod {m}}}
m
|
(
a
−
b
)
{\displaystyle m|(a-b)}
m
|
(
a
−
b
)
{\displaystyle m|(a-b)}
a
≡
b
(
mod
m
)
{\displaystyle a\equiv b{\pmod {m}}}
m
{\displaystyle m}
(
a
−
b
)
{\displaystyle (a-b)}
m
{\displaystyle m}
n
{\displaystyle n}
倍数 ：
m
=
c
×
n
{\displaystyle m=c\times n}
n
|
m
{\displaystyle n|m}
m
|
(
a
−
b
)
{\displaystyle m|(a-b)}
n
|
(
a
−
b
)
⇒
a
≡
b
(
mod
n
)
{\displaystyle n|(a-b)\Rightarrow a\equiv b{\pmod {n}}}
a
≡
b
(
mod
c
n
)
⇒
a
≡
b
(
mod
n
)
{\displaystyle a\equiv b{\pmod {cn}}\Rightarrow a\equiv b{\pmod {n}}}
a
≡
b
(
mod
m
)
n
|
m
}
⇒
a
≡
b
(
mod
n
)
{\displaystyle \left.{\begin{matrix}a\equiv b{\pmod {m}}\\n|m\end{matrix}}\right\}\Rightarrow a\equiv b{\pmod {n}}}
[ 注 1] 现假设
m
{\displaystyle m}
(
a
−
b
)
{\displaystyle (a-b)}
c
(
a
−
b
)
{\displaystyle c(a-b)}
m
{\displaystyle m}
c
{\displaystyle c}
(
m
,
c
)
=
1
{\displaystyle (m,c)=1}
m
{\displaystyle m}
(
a
−
b
)
{\displaystyle (a-b)}
m
|
(
a
−
b
)
⇒
a
≡
b
(
mod
m
)
{\displaystyle m|(a-b)\Rightarrow a\equiv b{\pmod {m}}}
a
c
≡
b
c
(
mod
m
)
(
c
,
m
)
=
1
}
⇒
a
≡
b
(
mod
m
)
{\displaystyle \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
)
{\displaystyle m_{1}|(a-b)}
m
2
|
(
a
−
b
)
{\displaystyle m_{2}|(a-b)}
m
1
{\displaystyle m_{1}}
m
2
{\displaystyle m_{2}}
最小公倍数 必定可以整除
(
a
−
b
)
{\displaystyle (a-b)}
a
≡
b
(
mod
[
m
1
,
m
2
]
)
{\displaystyle a\equiv b{\pmod {[m_{1},m_{2}]}}}
a
≡
b
(
mod
m
1
)
a
≡
b
(
mod
m
2
)
⋮
a
≡
b
(
mod
m
n
)
(
n
≥
2
)
}
⇒
a
≡
b
(
mod
[
m
1
,
m
2
,
⋯
,
m
n
]
)
{\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的正整数
q
{\displaystyle q}
素数 幂的乘积：
q
=
p
1
c
1
×
p
2
c
2
×
.
.
.
×
p
n
c
n
{\displaystyle q=p_{1}^{c_{1}}\times p_{2}^{c_{2}}\times ...\times p_{n}^{c_{n}}}
p
i
{\displaystyle p_{i}}
c
i
>
0
{\displaystyle c_{i}>0}
S
q
{\displaystyle S_{q}}
q
{\displaystyle q}
S
q
=
{
p
1
,
p
1
2
,
⋯
,
p
1
c
1
,
p
2
,
p
2
2
,
⋯
,
p
2
c
2
,
⋯
,
p
n
,
p
n
2
,
⋯
,
p
n
c
n
}
{\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}}\}}
r
{\displaystyle r}
r
{\displaystyle r}
q
{\displaystyle q}
S
r
{\displaystyle S_{r}}
S
q
{\displaystyle S_{q}}
子集 。令
m
1
|
q
{\displaystyle m_{1}|q}
m
2
|
q
{\displaystyle m_{2}|q}
S
m
1
{\displaystyle S_{m_{1}}}
S
m
2
{\displaystyle S_{m_{2}}}
并集 必定也是
S
q
{\displaystyle S_{q}}
元素 ，它们的乘积就是
m
1
{\displaystyle m_{1}}
m
2
{\displaystyle m_{2}}
最小公倍数
[
m
1
,
m
2
]
{\displaystyle [m_{1},m_{2}]}
S
[
m
1
,
m
2
]
=
S
m
1
∪
S
m
2
{\displaystyle S_{[m_{1},m_{2}]}=S_{m_{1}}\cup S_{m_{2}}}
[
m
1
,
m
2
]
{\displaystyle [m_{1},m_{2}]}
q
{\displaystyle q}
(
p
−
1
)
!
≡
−
1
(
mod
p
)
{\displaystyle (p-1)!\ \equiv \ -1\ ({\mbox{mod}}\ p)}
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1{\pmod {p}}}
a
φ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}
a
λ
(
n
)
≡
1
(
mod
n
)
{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}
(
x
)
k
≡
x
(
x
−
1
)
(
x
−
2
)
⋯
(
x
−
k
+
1
)
≡
0
(
mod
k
!
)
{\displaystyle (x)_{k}\equiv x(x-1)(x-2)\cdots (x-k+1)\equiv 0{\pmod {k!}}}
(
m
n
)
≡
∏
i
=
0
k
(
m
i
n
i
)
(
mod
p
)
,
{\displaystyle {\binom {m}{n}}\equiv \prod _{i=0}^{k}{\binom {m_{i}}{n_{i}}}{\pmod {p}},}
(
m
+
p
k
+
[
l
o
g
p
n
]
n
)
≡
(
m
n
)
(
mod
p
k
)
{\displaystyle {\binom {m+p^{k+[log_{p}n]}}{n}}\equiv {\binom {m}{n}}{\pmod {p^{k}}}}
设
N
=
∏
i
p
i
k
i
{\displaystyle N=\prod _{i}p_{i}^{k_{i}}}
(
m
+
L
(
n
,
N
)
n
)
≡
(
m
n
)
(
mod
N
)
{\displaystyle {\binom {m+L(n,N)}{n}}\equiv {\binom {m}{n}}{\pmod {N}}}
L
(
n
,
N
)
=
∏
i
p
i
k
i
+
[
l
o
g
p
n
]
=
N
∏
i
p
i
[
l
o
g
p
n
]
{\displaystyle L(n,N)=\prod _{i}p_{i}^{k_{i}+[log_{p}n]}=N\prod _{i}p_{i}^{[log_{p}n]}}
[ 7]
a
−
1
a
˙
≡
1
(
mod
n
)
{\displaystyle a^{-1}{\dot {a}}\equiv 1{\pmod {n}}}
可用辗转相除法 、欧拉定理 、卡迈克尔函数 求解。
存在最小的正整数d使得
a
d
≡
1
(
mod
n
)
{\displaystyle a^{d}\equiv 1{\pmod {n}}}
d
=
φ
(
n
)
{\displaystyle d=\varphi (n)}
a
x
≡
b
(
mod
n
)
{\displaystyle ax\equiv b{\pmod {n}}}
考虑最大公约数 ，有解时用辗转相除法 等方法求解。
{
a
1
x
≡
b
1
(
mod
m
1
)
a
2
x
≡
b
2
(
mod
m
2
)
⋮
a
n
x
≡
b
n
(
mod
m
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}}}
先求解每一个线性同余方程，再用中国剩余定理 解方程组。
x
2
≡
d
(
mod
p
)
{\displaystyle x^{2}\equiv d{\pmod {p}}}
勒让德符号 、雅可比符号 、克罗内克符号 、二次互反律 用于判别d是否为模n的二次剩余。
x
n
≡
d
(
mod
p
)
{\displaystyle x^{n}\equiv d{\pmod {p}}}
求自然数 a的个位数字，就是求a与哪一个数对于模10同余。
10
≡
1
(
mod
3
)
,
10
n
≡
1
(
mod
3
)
,
10001
≡
10
4
+
1
≡
1
+
1
(
mod
3
)
{\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 ;
}
![{\displaystyle \mathbb {Z} [i]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/9ffa94e9e2e6d9e5e5373d5fafb954b902743fde)
![{\displaystyle \mathbb {Z} [\omega ]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/7ae955a9a0d0f342fc73aaafe28af604d23267f7)
![{\displaystyle [a\equiv b{\pmod {m}}]\Rightarrow [b\equiv a{\pmod {m}}]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/784118bb799e130251676332bbc8575d4959054a)
![{\displaystyle {\big \{}[a\equiv b{\pmod {m}}]\wedge [b\equiv c{\pmod {m}}]{\big \}}\Rightarrow [a\equiv c{\pmod {m}}]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/c1bb86983490453007d873894f10a078827e03f9)
![{\displaystyle {[a]}_{m}:=\left\{z\in \mathbb {Z} \,{\big |}\,(\exists k\in \mathbb {Z} )(z=a+km)\right\}}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/5f73a5fa2bfe20a998278580218b5a2209db7484)
![{\displaystyle \displaystyle [a]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/8a5fadafb83911f2d4ff109493ef4f2325799806)
![{\displaystyle [0],[1],[2]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/193154b0aecfeb23ba10026370b42f07d922f56e)
![{\displaystyle a\equiv b{\pmod {[m_{1},m_{2}]}}}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/2db2270c3d18f32c4d9538fb9b2b19f48beecba3)
![{\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}]}}}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/5c2759d7ab80bb75e83875ea15fc5f84fad228a7)
![{\displaystyle [m_{1},m_{2}]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/d8b68f9cdd68d67339cfb790185addd80036ac28)
![{\displaystyle S_{[m_{1},m_{2}]}=S_{m_{1}}\cup S_{m_{2}}}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/79396926be816cd89765c883332c1380f84d60bb)
![{\displaystyle {\binom {m+p^{k+[log_{p}n]}}{n}}\equiv {\binom {m}{n}}{\pmod {p^{k}}}}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/09282d3a3f9ce294f37de1f9eb44aff4421c144a)
![{\displaystyle L(n,N)=\prod _{i}p_{i}^{k_{i}+[log_{p}n]}=N\prod _{i}p_{i}^{[log_{p}n]}}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/fb313c9aaf199527a5beeb6f1d59e2797a2bc9a5)
![{\displaystyle [m_{1},m_{2},\cdots ,m_{n}]}](https://wikimedia.org/zhwiki/api/rest_v1/media/math/render/svg/dceb2927ec6590cca6d4a38f70508c5485fe250f)
