同餘 （英語：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)
