可以证明所有对于模
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)}
以下为快速展示小于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/api/rest_v1/media/math/render/svg/9ffa94e9e2e6d9e5e5373d5fafb954b902743fde)
![{\displaystyle \mathbb {Z} [\omega ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ae955a9a0d0f342fc73aaafe28af604d23267f7)
![{\displaystyle [a\equiv b{\pmod {m}}]\Rightarrow [b\equiv a{\pmod {m}}]}](https://wikimedia.org/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/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/api/rest_v1/media/math/render/svg/5f73a5fa2bfe20a998278580218b5a2209db7484)
![{\displaystyle \displaystyle [a]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a5fadafb83911f2d4ff109493ef4f2325799806)
![{\displaystyle [0],[1],[2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/193154b0aecfeb23ba10026370b42f07d922f56e)
![{\displaystyle a\equiv b{\pmod {[m_{1},m_{2}]}}}](https://wikimedia.org/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/api/rest_v1/media/math/render/svg/5c2759d7ab80bb75e83875ea15fc5f84fad228a7)
![{\displaystyle [m_{1},m_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8b68f9cdd68d67339cfb790185addd80036ac28)
![{\displaystyle S_{[m_{1},m_{2}]}=S_{m_{1}}\cup S_{m_{2}}}](https://wikimedia.org/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/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/api/rest_v1/media/math/render/svg/fb313c9aaf199527a5beeb6f1d59e2797a2bc9a5)
![{\displaystyle [m_{1},m_{2},\cdots ,m_{n}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dceb2927ec6590cca6d4a38f70508c5485fe250f)
