同余定理
同余定理是数论中的重要概念。给定一个正整数
m
m
m
，如果两个整数
a
a
a
和
b
b
b
满足
(
a
−
b
)
(a-b)
(
a
−
b
)
能被
m
m
m
整除，那么我们就称整数
a
a
a
与
b
b
b
对模
m
m
m
同余，记作
a
≡
b
(
m
o
d
m
)
a\equiv b(mod \: m)
a
≡
b
(
m
o
d
m
)
。
自我理解：两个数同时除以
m
m
m
得到的余数相同。
一、同余
定义：设
m
m
m
是大于
1
1
1
的正整数，
a
,
b
a,b
a
,
b
是整数，如果
m
∣
(
a
−
b
)
m|(a-b)
m
∣
(
a
−
b
)
，则称
a
a
a
与
b
b
b
关于模
m
m
m
同余，记作
a
≡
b
(
m
o
d
m
)
a\equiv b(mod \: m)
a
≡
b
(
m
o
d
m
)
。
定理1
：整数
a
,
b
a,b
a
,
b
对模
m
m
m
同余的充要条件是
a
−
b
a-b
a
−
b
能被
m
m
m
整除（即
m
∣
a
−
b
m|a-b
m
∣
a
−
b
）。
推论
：
a
≡
b
(
m
o
d
m
)
a\equiv b(mod\:m)
a
≡
b
(
m
o
d
m
)
的充分条件是
a
=
m
×
t
+
b
a=m\times t+b
a
=
m
×
t
+
b
(
t
t
t
为整数)。
表示对模
m
m
m
同余关系的式子叫做模
m
m
m
的同余式，简称同余。
定理2
：同余关系具有反身性，对称性与传递性，即
-
a≡
a
(
m
o
d
m
)
a\equiv a(mod\:m)
a
≡
a
(
m
o
d
m
)
; -
若
a≡
b
(
m
o
d
m
)
a\equiv b(mod\:m)
a
≡
b
(
m
o
d
m
)
，则
b≡
a
(
m
o
d
m
)
b\equiv a(mod\:m)
b
≡
a
(
m
o
d
m
)
； -
若
a≡
b
(
m
o
d
m
)
,
b
≡
c
(
m
o
d
m
)
a\equiv b(mod\:m),b\equiv c(mod\:m)
a
≡
b
(
m
o
d
m
)
,
b
≡
c
(
m
o
d
m
)
，则
a≡
c
(
m
o
d
m
)
a\equiv c(mod\:m)
a
≡
c
(
m
o
d
m
)
。
定理3
：若
a
≡
b
(
m
o
d
m
)
,
c
≡
d
(
m
o
d
m
)
a\equiv b(mod\:m),c\equiv d(mod\:m)
a
≡
b
(
m
o
d
m
)
,
c
≡
d
(
m
o
d
m
)
，则
-
a+
c
≡
b
+
d
(
m
o
d
m
)
a+c\equiv b+d(mod\:m)
a
+
c
≡
b
+
d
(
m
o
d
m
)
； -
a−
c
≡
b
−
d
(
m
o
d
m
)
a-c\equiv b-d(mod\:m)
a
−
c
≡
b
−
d
(
m
o
d
m
)
; -
a×
c
≡
b
×
d
(
m
o
d
m
)
a\times c\equiv b\times d(mod\:m)
a
×
c
≡
b
×
d
(
m
o
d
m
)
.
对于多个的同模同余式也能进行加减乘运算。对于乘法运算还有一下推论：
推论
：若
a
≡
b
(
m
o
d
m
)
a\equiv b(mod\:m)
a
≡
b
(
m
o
d
m
)
，
n
n
n
为自然数，则
a
×
n
≡
b
×
n
(
m
o
d
m
)
a\times n\equiv b\times n(mod\:m)
a
×
n
≡
b
×
n
(
m
o
d
m
)
。
定理4
：若
c
×
a
≡
c
×
b
(
m
o
d
m
)
,
(
c
,
m
)
=
d
c\times a\equiv c \times b(mod\:m),(c,m)=d
c
×
a
≡
c
×
b
(
m
o
d
m
)
,
(
c
,
m
)
=
d
，且
a
,
b
a,b
a
,
b
为整数，则
a
≡
b
(
m
o
d
m
d
)
a\equiv b(mod\:\frac{m}{d})
a
≡
b
(
m
o
d
d
m
)
。
推论
：若
c
×
a
≡
c
×
b
(
m
o
d
m
)
,
(
c
,
m
)
=
1
c\times a\equiv c\times b(mod\:m),(c,m)=1
c
×
a
≡
c
×
b
(
m
o
d
m
)
,
(
c
,
m
)
=
1
，且
a
,
b
a,b
a
,
b
为整数，则
a
≡
b
(
m
o
d
m
)
a\equiv b(mod\:m)
a
≡
b
(
m
o
d
m
)
。
定理5
：若
a
≡
b
(
m
o
d
m
)
,
a
≡
b
(
m
o
d
n
)
a\equiv b(mod\:m),a\equiv b(mod\:n)
a
≡
b
(
m
o
d
m
)
,
a
≡
b
(
m
o
d
n
)
，则
a
≡
b
(
m
o
d
[
m
,
n
]
)
a\equiv b(mod\:[m,n])
a
≡
b
(
m
o
d
[
m
,
n
])
。
推论
：若
a
≡
b
(
m
o
d
m
i
)
,
i
=
1
,
2
,
…
,
n
a\equiv b(mod\:m_i),i=1,2,\dots,n
a
≡
b
(
m
o
d
m
i
)
,
i
=
1
,
2
,
…
,
n
，则
a
≡
b
(
m
o
d
[
m
1
,
m
2
,
…
,
m
n
]
)
a\equiv b(mod\:[m_1,m_2,\dots,m_n])
a
≡
b
(
m
o
d
[
m
1
,
m
2
,
…
,
m
n
])
。
定理6
：若
a
≡
b
(
m
o
d
m
)
,
n
∣
m
a\equiv b(mod\:m),n|m
a
≡
b
(
m
o
d
m
)
,
n
∣
m
，则
a
≡
b
(
m
o
d
n
)
a\equiv b(mod\:n)
a
≡
b
(
m
o
d
n
)
。
定理7
：若
a
≡
b
(
m
o
d
m
)
a\equiv b(mod\:m)
a
≡
b
(
m
o
d
m
)
,那么
a
n
≡
b
n
(
m
o
d
m
)
a^n\equiv b^n(mod\:m)
a
n
≡
b
n
(
m
o
d
m
)
。
同余证一些特殊数的整除特征
：
-
正整数
aa
a
是
99
9
的倍数必须且只须
aa
a
的各位数码之和是
99
9
的倍数。 -
设
a=
a
n
a
n
−
1
…
a
1
a
0
a=a_na_{n-1}\dots a_1a_0
a
=
a
n
a
n
−
1
…
a
1
a
0
，
11∣
a
11|a
11∣
a
的充要条件是
11∣
a
0
−
a
1
+
a
2
−
⋯
+
(
−
1
)
n
a
n
11|a_0-a_1+a_2-\dots+(-1)^na_n
11∣
a
0
−
a
1
+
a
2
−
⋯
+
(
−
1
)
n
a
n
。 -
正整数
aa
a
能被
77
7
整除的条件是
a0
−
a
1
+
a
2
−
⋯
+
(
−
1
)
n
a
n
≡
0
(
m
o
d
7
)
a_0-a_1+a_2-\dots+(-1)^na_n\equiv0(mod\:7)
a
0
−
a
1
+
a
2
−
⋯
+
(
−
1
)
n
a
n
≡
0
(
m
o
d
7
)
,这里的
a1
a_1
a
1
为三位数（千进制）。
定义2
：如果
m
m
m
为自然数，集合
k
i
=
{
x
∣
x
=
m
×
t
+
i
,
i
是任意整数
}
，
r
=
0
,
1
,
…
,
n
k_i=\{x|x=m\times t+i,i是任意整数\}，r=0,1,\dots,n
k
i
=
{
x
∣
x
=
m
×
t
+
i
,
i
是任意整数
}
，
r
=
0
,
1
,
…
,
n
。则称
k
0
,
k
1
,
…
,
k
m
−
1
k_0,k_1,\dots,k_{m-1}
k
0
,
k
1
,
…
,
k
m
−
1
为模
m
m
m
的剩余类。
剩余类具有如下比较明显的性质：
-
模
mm
m
的剩余类
k0
,
k
1
,
…
,
k
m
−
1
k_0,k_1,\dots,k_{m-1}
k
0
,
k
1
,
…
,
k
m
−
1
都是整数的非空子集； - 每个整数必属于一个剩余类；
-
两个整数属于同一个剩余类的充要条件是它们对模
mm
m
同余。
定义3
：从模
m
m
m
的每个剩余类中任取一个数，所得到的
m
m
m
的个数叫做模
m
m
m
的完全剩余系。
定理6
：
k
k
k
个整数
a
1
,
a
2
,
…
,
a
k
a_1,a_2,\dots,a_k
a
1
,
a
2
,
…
,
a
k
构成模
m
m
m
的完全剩余系的充要条件是
k
=
m
k=m
k
=
m
，且这
m
m
m
个数对模
m
m
m
两两不同余。
定理7
：若
x
1
,
x
2
,
…
,
x
m
x_1,x_2,\dots,x_m
x
1
,
x
2
,
…
,
x
m
是模
m
m
m
的完全剩余系，
(
a
,
m
)
=
1
,
b
(a,m)=1,b
(
a
,
m
)
=
1
,
b
为整数，则
a
×
x
1
+
b
,
a
×
x
2
+
b
,
…
,
a
×
x
m
+
b
a\times x_1+b,a\times x_2+b,\dots,a\times x_m+b
a
×
x
1
+
b
,
a
×
x
2
+
b
,
…
,
a
×
x
m
+
b
也是模
m
m
m
的完全剩余系。