千古风流人物-上海职称英语考试

第二章 同余理论
2.1 同余的概念和基本性质
【定义2.1.1】给定一个正整数m，两个整数a、b叫做模m同余，如果a －b被
m整除，或
m|ab
，记作
ab


m od
否则叫做模m不同余，记作a≠b
m

；
（（mod m））
【注】由于
m|ab
等价于
m|ab
，所以同余式
ab


modm

等价于
ab

mod

m

，
故以后总假定模
m1
。
【例1】 7│28＝29－1，故29≡1（mod 7）；
7│21＝27－6，故27≡6（mod 7）；
7│28＝23－（－5），故23≡－5（mod 7）；
同余运算的相关性质：
【性质1】设m是一个正整数，a、b是两个整数，则a≡b（mod m）

存在整
数k，使得a＝b＋km。
（证）a≡b（mod m）


m|ab


存在k，使得 a－b＝km，即a＝b＋km

【性质2】同余是一种等价关系。即
自反性：a≡a（mod m）
对称性：a≡b（mod m）

b≡a （mod m）
传递性：a≡b（mod m）且b≡c （mod m）

a≡c （mod m）
（证）（i）m│0＝a－a

a≡a（mod m）
（ii）a≡b （mod m）

m│a－b

m│b－a＝－(a－b)

b≡a （mod m）
（iii）a≡b（mod m），b≡c（mod m）

m│a－b，m│b－c

m│(a－b)＋ (b－c)＝a－c

a≡c （mod m）


【性质3】（等价定义）整数a、b模m同余

a、b被m除的余数相同。
（证）由欧几里得除法，存在q，r，
q

，
r

，使得
a
＝qm＋r，b＝
q

m＋
r


即 a－b＝(q－
q

)m＋(r－
r

)
或 （r－
r

）＝(a－b)－ (q－
q

)m

故 m│(a－b)

m│(r－
r

)
但 0≢│r－
r

│＜m 且m│(r－
r

)

r－
r

＝0
故 m│(a－b)

r－
r

＝0，即r＝
r



【性质4】设m为正整数，a、b、c、d为整数，若
a≡b （mod m）， c≡d （mod m）则
（i）
（ii）
a＋c≡b＋d （mod m）；
ac≡bd （mod m）。
（证）已知a≡b（mod m）且 c≡d（mod m）

a＝b＋hm且c＝d＋km

a＋c＝(b＋hm)＋( d＋km)＝b＋d＋(h＋k)m，
ac＝(b＋hm)( d＋km)＝bd＋(hd＋kb＋hkm)m

由性质1即得结论。

一般情形：
a
i
b
i
（mod m）（i＝1,2,…,k），则
kk
（i）

a
i
i1
k

b
i
（mod m）
i1
k
i1
（ii）

a
i


b
i
（mod m）
i1

【推论1】a≡b （mod m）

na≡nb （mod m），其中n为正整数。
【推论2】a≡b （mod m）


a
n
b
n
（mod m），其中n为正整数。
【推论3】x≡y （mod m），
a
i
b
i
（mod m）（i＝1,2,…,k），
则
a
0
a
1
xa
2
xa
k
x
≡
b
0
b1
yb
2
yb
k
y
（mod m）




【例6】2003年5月9日是星期五，问此后的第2
2003
天是星期几？

2k2k

（解） 2
2003
＋5≡
2
6 672

3
667
2
2
＋5 (mod 7）
≡
12
＋5 (mod 7））
≡9 (mod 7）
≡2 (mod 7）

【例7】设十进制整数n＝
a
k
a
k 1

a
1
a
0
，则
3│n

3│
a
k
a
k1


a
1
a
0

9│n

9│
a
k
a
k1


a
1
a
0

（证）因
n＝
a
k
10
n＝
a
k
10
k< br>a
1
10a
0
≡
a
k
a
k1


a
1
a
0
(mod 3)
a
1
10a
0
≡
a
k
a
k1


a
1
a
0
(mod 9)
k

【例8】设整数n的1000进制表示式为
n＝
a
k
1000
k
则7（或11，或13）│n

7（或11，或13）│

a
0
a
2


－

a
1
a
3



（证）因
n＝
a
k
1000
k
 a
1
1000a
0

a
1
1000a
0

k1
k1
≡
a
k

1

a
k1

1

n≡
a
k

1

a
k 1

1

n≡
a
k

1

a
k1

1

k
k
k
< br>
a
1

1

a
0
mod 7


a
1

1

a
0
mod 11


a
1

 1

a
0
mod 13
k1
例如，判断n＝12345678能否被7(或11，或13)整除：
12345678＝12×1000
2
+345×1000+678
而 (12+678)－345＝345不能被7、11、13整除
故1234567不能被这3个数整除。

【例9】设十进制整数n＝
a< br>k
a
k1

a
1
a
0
，则
11│n

11│

a
0
a
2

－

a
1
a
3



2│n

2│
a
0

4│n

4│
a
1
a
0


4│
2a
1
a
0

8│n

8│
a
2
a
1
a
0


8│
4a
2
2a
1
a
0

2
│n


2
│
a
i1
< br>a
1
a
0

ii

例如，判断n＝981234576能否被11、2、4、8、16整除。
因为（6+5+3+1+9）－（7+4+2+8）＝3，故n不能被11整除
因2│6，故2│n
4├76或4├2×7+6＝22，故4├n
8│4×5+2×7+6＝40，故8│n
因8×4+4×5+10×7+6≡0 mod 16，故16│n

【性质5】消去律：设ad≡bd （mod m）。若（d，m）＝1，则
a≡b （mod m）。
（证）ad≡bd （mod m）

m│ad－ bd＝(a－b)d
而（d，m）＝1，故m│(a－b)，即 a≡b （mod m）

【例10】95≡25 (mod 7)，且（5，7）＝1，故19≡5(mod 7)

【反例11】115≡25 (mod 15)，即23×5≡5×5(mod 15)，但23≠5(mod 15)
因为（5，15）＝5＞1


【性质6】a≡b （mod m）且k＞0，则ak≡bk （mod mk）
（证）a≡b （mod m）

m│a－ b

mk│(a－b)k＝ak－bk

ak≡bk （mod mk）

【例12】19≡5 (mod 7)，k＝4＞0，所以76≡20 (mod 28)

【性质7】a≡b （mod m）且d│m，则
a≡b mod d
（证）a≡b （mod m）

m│a－b
又 d│m

d│a－b
即 a≡b mod d

另有一些性质，这里就不再一一列举，有兴趣的同学可参阅相关参考书。

2.2剩余类和完全剩余系
设m为正整数，记
C
a
＝
< br>ccZ,ac(modm)


C
a
非空，至少a∈
C
a

。

【定理2.2.1】设m是一个正整数，则
（i）
（ii）
任一整数必包含在某个
C
r
中，0≢r≢m－1
C
a
＝
C
b


a≡b （mod m）
a
（iii）
C


C
b
＝φ

a≠b （mod m）
【定义2.2.1】
C
a
叫做模m的a的剩余类。
一个剩余类中的任一个数叫做该类的剩余或代表。
若
r
0
,r1
,,r
m1
是m个整数，且其中任何两个都不在同一个剩余类中，则称r
0
,r
1
,,r
m1
为模m的一个完全剩余系。
【注】每个剩余类中都包含了无穷多个整数，而完全剩余系则恰好由m个数组
成。

模m的剩余类共有m个，例如
C
0
,

C
1
,,C
m1

【例13】设m＝10，则
C
a
＝

a10kkZ


是模m＝10的剩余类。

模10的完全剩余系举例：
（1）0，1，2，…，9
（2）1，2，3，…，10
（3）0，－1，－2，…，－9
（4）0，3，6，9，…，27
（5）10，11，22，33，44，…，99
（6）20，1，－18，13，64，－55，－94，－3，18，9

剩余类和完全剩余系的相关性质：
【定理2.2.2】整数
r
0
, r
1
,,r
m1
为m的一个完全剩余系

r
i
r
j
mod m。
其中（0≢i＜j≢m－1）
【例14】m的典型完全剩余系：
最小非负完全剩余系：0，1，…，m－1
最小正完全剩余系：1，2，…，m
最大非正完全剩余系：0，－1，…，－(m－1)
最大负完全剩余系：－1，－2，…，－m

【定理2.2.3】设a是满足(a， m)＝1的整数，b为任意整数。若x遍历模m的

一个完全剩余系，则ax＋b遍历模m 的一个完全剩余系。
（证）设
r
0
,r
1
,,r
m1
为m的一个完全剩余系。
由定理2.2.2知，
r
i
r
j
（mod m） （0≢i＜j≢m－1）
又(a，m)＝1，故
ar
i
ar
j
（mod m）
从而
ar
i
bar
j
b
（mod m）
由定 理2.2.2，
ar
0
b
，
ar
1
b
，…，
ar
m1
b
，是模m的一个完全剩余系。
【例15】（例3）设m＝10，原剩余系为0，1，…，9。
当a＝7，b＝5时，新的剩余系为：5，12，17，…，68
当a＝3，b＝6时，新的剩余系为：6，9，12，…，33


【定理2.2.4】设
m
1
,m
2
是 两个互素的正整数，若
x
1
,x
2
分别遍历
m
1< br>,m
2
的完全剩余系，则
m
2
x
1
m1
x
2
遍历模
m
1
m
2
的完全剩余系 。
x
2
分别遍历
m
1
,m
2
个整数时，
m
2
x
1
m
1
x
2
遍历
m
1
m
2
（证）当
x
1
,
个整数。 < br>问题转化为：证明
m
1
m
2
个整数
m
2x
1
m
1
x
2
模
m
1
m< br>2
两两不同余。
用反证法：若存在
x
1
,x
2和
y
1
,y
2
满足
m
2
x
1
m
1
x
2
≡
m
2
y
1
m
1
y
2
mod
m
1
m
2

则由2.1节性质7知
m
2
x
1
m
1
x
2
≡
m
2
y
1
m
1
y
2
mod
m
1

即
m
2
x
1
≡
m
2
y
1
mod
m
1

而（m
1
,m
2
）＝1，故由同余的性质知
x
1
≡
y
1
mod
m
1

同理可证，
x
2
≡
y
2
mod
m
2
。


【例16】设p、q是两个不同的素数，n＝ pq，则对任意整数c，存在唯一的一
对数x和y，满足
qx＋py＝c （mod n）， 0≢x＜p，0≢y＜q
（证）首先知p、q互素。
再由定理2.2.4，当 x、y分别遍历模p、q的完全剩余系时，qx＋py遍历模n
＝pq的完全剩余系。故存在唯一的一对 整数x、y，满足上式。

2.3简化剩余系和欧拉函数
【定义2 .3.1】（定义1）设n为正整数，则1,2,…,n中与n互素的整数的个
数，记作
(n)，叫做欧拉（Euler）函数。

【例17】（例1）设n＝10，则1,2,…,10中与10互素的数为
1,2,7,9，故

(10)＝4

【例18】
(1)＝1，

(2)＝1，

(3)＝2，

(4) ＝2，

(6)＝2，即1,2,…,6中与6互素的数为1，5

(2 0)＝8，即1,2,…,20中与20互素的数为1,3,7,9,11,13,17,19

欧拉函数的若干性质：
【性质1】设p为素数，则

(p)＝p－1。


1

【性质2】设p为素数，且整数α≣1，则
(
p
)＝
p


1



p



证明：（证）1,2,…,
p
中与p 不互素的数共有
p
p，2p，3p，4p，…，
p
由此即

(
p
)＝
p



1
个，这些数是

1
P


p

1
＝< br>p

1

p1

＝
p



1


1



。
p


【性质3】设整数n＝pq，其中p，q为不同的素数，则

(n)＝

(pq)＝

(p)

(q)＝(p －1)(q－1)
（证）设整数a满足1≢a≢n，若(a，n)＝d＞1，则必有
d
＝sp或d＝tq （因为n的因数只有1，p，q，pq＝n）
即必有 p│d或q│d，从而有p│a或q│a
这说明与n不互素的数a必为a＝sp或a＝tq.
这样的 a为
p，2p，3p，4p，…，(q－1)p，qp
和q，2q，3q，4q，…，(p－1)q，pq
共有p＋q－1个
∴

(n)＝

(pq)＝pq－(p＋q－1)＝(p－1)(q－1) ＝

(p)

(q)

【例19】

(143)＝

(11·13)＝

(11)

(13)＝10·12＝120

【性质4】设整数n＝
pq
，其中p，q为不同的素数，则




(n)＝

(
pq
)＝

(
p
)

(
q
)＝
n


1



1

1


1


p

q

证明：略
< br>【推论】设整数n有标准分解式
p
1
1
p
2
2

p
k
k
，则



(n)＝n

pn


1

1

1


1





11


1

1


＝
n



p
1

p
2


p
k

p



【例20】

(100)＝

1
22
(2·5)＝100

2 5

4
＝40

(360)＝



1
32
(2·3·5)＝360
24

＝96
235
【性质5】欧拉函数


n

是乘性函数（或称积 性函数）。即若正整数m，n互
素，则

(mn)＝

(m)

(n)。
（证）记m、n的标准分解式分别为

m
＝
p
1
1
p
2
2

p
k
k
，n＝
q
1
1
q
2
2

q
j< br>j

则

1

2

j

(mn)＝

p
1
p
2
p
k
k
q
1
1
q
2
2
q
j








1


1


1


1





1



1
＝
mn


1
p




< br>
1
p


q
1


q
j


1


k


 

1


1


1


1





1

1n1

1
＝
m



p
1

p
k

q
1

qj








＝< br>
(m)

(n)

【例21】设m＝33，n＝32，求

(33·32)。
（解）(33，32)＝1，故

(33·32)＝

(33)

(32)＝ 33

1
210
·32

＝160

3112

【定义2.3.2】一个模m的剩余类叫做简化剩余类（或互素 剩余类、既约剩余类、
不可约剩余类），如果该类中存在一个与m互素的剩余。
注：本定义与剩余的选取无关。
比如：对于 m=20而言，
C
3
，
C
7
都是20的简化剩余类，
C
15
却不是


【定理2.3.1】设
r
1
、
r
2
是同 一剩余类中的两个剩余，则
r
1
与m互素的充分必
要条件是
r
2
与m互素。
（证）由题设知
r
1
＝
r
2
＋km
再由最大公因子性质知（r
1
，m）＝（
r
2
，m）
∴ （
r
1
，m）＝1

（
r
2
，m）＝1

【定义2.3.3】设m为正整数，在模m的所有不同简化剩余类中，从每个类任取
一个数组成的整数集合，叫做模m的一个简化剩余系（或称为缩系、互素剩余
系、既约剩余系、不可约剩 余系）。
【例22】模6的简化剩余系为1，5
模20的简化剩余系为1,3,7,9,11,13,17,19

【定理2.3.2】m的简化剩余系的元素个数为


m


【例23】素数p的简化剩余系为 1，2，……，p－1，即


p

＝p－1

【定理2.3.3】设整数
r
1
，
r
2
，…，
r


m

均与m互素，且两两模m不同余，则
它们构成模m的一个简化剩余系。

【定理2.3.4】设整数
r
1
，
r
2
，…，
r


m

均与m互素，若它们构成模m的一个简化剩余系，则这些
r
i
必两两模m不同余。

（证）由 题意知
r
1
，
r
2
，…，
r


m

是来自模m的不同简化剩余类的剩余，而不
同剩余类中的数必互不同余。

【推论】设整数
r
1
，
r
2
，…，r


m

均与m互素，则它们构成模m的简化剩余系
的充分必要条件是这些
r
i
两两模m不同余。

【定理2.3.5 】设m为正整数，a是满足(a，m)＝1的整数。那么，若x遍历模
m的一个简化剩余系，则ax也遍 历模m的一个简化剩余系。
（证）首先，由(a，m)＝1及(x，m)＝1知(ax，m)＝1，即 ax是简化剩余类的
剩余。其次，若
x
1
x
2
（mod m），则必有
ax
1
ax
2
（mod m）（否则，
由
ax
1
ax
2
（mod m）及(a，m)＝1可得
x
1
x
2
（mod m），矛盾）
因此x遍历模m的一个简化剩余系时，ax遍历


m

个 数，且它们两两m不同余。
由定理2.3.3知ax也遍历模m的一个简化剩余系。

【例24】（例7）已知1，7，11，13，17，19，23，29是模30的简化剩余系，
(7 ，30)＝1，则7，49，77，91，119，133，161，203也是模30的简化剩余系。


【定理2.3.6】设m为正整数，a是满足(a，m)＝1的整数。则存在整数
a

（1≢
a

＜m）使得
aa

≡1 （mod m）
（证）（构造性证明）由(a，m)＝1知存在整数s，t，使得
sa＋tm＝(a，m)＝1
即
sa－1＝(－t)m
因此，所求
a

＝s。
【例25】设m＝737，a＝635，求
a

，满足
aa＇≡1 （mod m）
（解）利用广义欧几里得除法，可找到s＝－224，t＝193，使得
(－224) ·635＋193·737＝1
∴ a＇≡－224≡513 （mod 737）
即 635·(－224) ≡1 （mod 737）

【定义2.3.4】将定理2.3.7中满足条件的< br>a

叫作a（对模m）的逆，记为
a
即
aa
1
≡1 mod m

实质上，a与
a
1
1
。
互为逆元素。

【例26】对任何模数m＞1而言，至少有两个数有逆。即
1
≡1，

m1

1
1
≡m－1（mod m）
（或

1

≡－1）

关于模逆元的性质：
【性质1】若a模m可逆，则（a，m）=1。
（证）a可逆，则a的逆
a
1
1
存在，且满足
1
a
a
即存在整数k，使得a
a
1
≡1 （mod m）
=1＋km= km＋1
1
再由最大公因子的性质知（a
a
1
，m）=（m，1）=1
1
而 （a
a
，m）=1

（a，m）=1且（
a
，m）=1
【推论】a模m可逆的充分必要条件是（a，m）=1。

【性质2】
a
意整数。
1
不唯一。即若
a
1
存在，则
a
1
＋km都是a的逆，其中k为任
（证）只需直接验证 ：已知
a
1
是a的逆，即
≡1 （mod m）
a
a
那么，对任意整数k，有
a(
a
1
1
＋km) ≡a
a
1
＋ akm≡a
a
1
＋0≡1 （mod m）

【例27】m＝7，a＝2，直接计算有
……，
2·(－3)≡1 （mod 7）
2·4≡1 （mod 7）

2·11≡1 （mod 7）
2·18≡1 （mod 7）
……
即对模7而言，整数4＋7k都是2的逆（k∈z）

【性质3】若b和c都是a的逆，则有b≡c （mod m）。
（证）已知ab≡1 （mod m）， ac≡1 （mod m）
从而 ab≡ac （mod m）
而(a,m)＝1，故由消去律知 b≡c （mod m）。

【推论1】设整数a有逆
a
1
，则整数b是a的逆的充分必要条件是
1
b≡
a
即b＝
a
1
（mod m）。
+km（k∈z）。
1
（证）只要验证当b≡
a
（mod m）时，b也是a的逆即可。显然。
反之，20≠17 mod 50，则20不是3的逆。

【推论2】在模m的一个简化剩余系中，a的逆
a
1
是唯一的。
1
【例28】m＝7，选模7的最小正简化剩余系{1，2，…，6}，则a＝2的逆
2
4且唯一。
[性质4】（1）
a
＝

1
1
≡a。 （2）

a
1
a
2
a
k
（证）直接 验证即可。

【推论】
a

1
≡
a
1
1
a
2
1
a
k
1


n
1
≡
a

1

n
。

【例】设m＝55，求8和24模55的逆。
（解）首先可以观察出2模55的逆为
2
所以
8
1
1
＝28
≡
2

3
1
≡
2

1

3
≡
28
≡7 mod 55
3

24
1
≡
23
1

3

1
≡
2

1
33
1
≡
2

3
1
3
1≡
28
·37≡39
3

计算
a
的方法
【方法1】利用简化剩余类的性质枚举求逆
例 m＝11，a＝5，则
5·1≡5， 5·2≡10， 5·3≡4， 5·5≡3，
5·6≡8， 5·9≡1
∴
5
＝9 mod 11
【方法2】利用辗转相除法
【方法3】利用欧拉函数和欧拉定理的结论

2.4欧拉定理与费马小定理
【定理2.4.1】（Euler定理）设m是大于1的整数，若整数a满足(a，m)＝1，
则有
1
a
≡1 （mod m）
（证）设
r
1
, r
2
,

,r


m

为m的最 小正简化剩余系，则当(a，m)＝1时，


m

ar
1
,ar
2
,

,ar


m


也为模m的一个简化剩余系。故
ar
1
,ar
2
,

,ar


m

是模m的最小正剩余
r
1
,r
2
,

,r


m
的某个排列。所以
ar
1
ar
2

ar


m

≡
r
1
r
2

r


m

（mod m）
即
a


m



m


r r
12

r


m


≡
r
1
r
2

r


m

（mod m）
又由(
r
i
，m)＝1知，(
r
1
r
2

r


m

，m)＝1， 故有
a
≡1 （mod m）
【定理2.4.2】（Fermat定理）（定理2）设p为素数，a为任意正整数，则
a
≡a （mod p）
（证）(1)
pa
，则有
a
≡0 （mod p）


a
≡0 （mod p）
即
a
≡a （mod p）
(2) p├a，必有(a,p)＝1，由定理2.4.1
p1
p
p
p
a
≡1 （mod p）

两边同乘以a，得
a
≡a （mod p）

【例】设p＝11，a＝2，则

(11)＝10，故
p
2
≡2 mod 11
设p＝23，a＝10，则

(23)＝22，故
11
10
23
≡10 mod 23

【推论】设m＞1，则m为素数的必要条件是：对某个m├a的整数a，有
a
m1
≡1 （mod m）
应用：用于否定一个整数为素数。
意义：是判断一个正整数为素数的概率算法的理论基础

第二章 同余理论
2.1 同余的概念和基本性质
【定义2.1.1】给定一个正 整数m，两个整数a、b叫做模m同余，如果a－b被
m整除，或
m|ab
，记作< br>ab


mod
否则叫做模m不同余，记作a≠b
m

；
（（mod m））
【注】由于
m|ab
等价于
m|ab
，所以同余式
ab


modm

等价于
ab

mod

m

，
故以后总假定模
m1
。
【例1】 7│28＝29－1，故29≡1（mod 7）；
7│21＝27－6，故27≡6（mod 7）；
7│28＝23－（－5），故23≡－5（mod 7）；
同余运算的相关性质：
【性质1】设m是一个正整数，a、b是两个整数，则a≡b（mod m）

存在整
数k，使得a＝b＋km。
（证）a≡b（mod m）


m|ab


存在k，使得 a－b＝km，即a＝b＋km

【性质2】同余是一种等价关系。即
自反性：a≡a（mod m）
对称性：a≡b（mod m）

b≡a （mod m）
传递性：a≡b（mod m）且b≡c （mod m）

a≡c （mod m）
（证）（i）m│0＝a－a

a≡a（mod m）
（ii）a≡b （mod m）

m│a－b

m│b－a＝－(a－b)

b≡a （mod m）
（iii）a≡b（mod m），b≡c（mod m）

m│a－b，m│b－c

m│(a－b)＋ (b－c)＝a－c

a≡c （mod m）


【性质3】（等价定义）整数a、b模m同余

a、b被m除的余数相同。
（证）由欧几里得除法，存在q，r，
q

，
r

，使得
a
＝qm＋r，b＝
q

m＋
r


即 a－b＝(q－
q

)m＋(r－
r

)
或 （r－
r

）＝(a－b)－ (q－
q

)m

故 m│(a－b)

m│(r－
r

)
但 0≢│r－
r

│＜m 且m│(r－
r

)

r－
r

＝0
故 m│(a－b)

r－
r

＝0，即r＝
r



【性质4】设m为正整数，a、b、c、d为整数，若
a≡b （mod m）， c≡d （mod m）则
（i）
（ii）
a＋c≡b＋d （mod m）；
ac≡bd （mod m）。
（证）已知a≡b（mod m）且 c≡d（mod m）

a＝b＋hm且c＝d＋km

a＋c＝(b＋hm)＋( d＋km)＝b＋d＋(h＋k)m，
ac＝(b＋hm)( d＋km)＝bd＋(hd＋kb＋hkm)m

由性质1即得结论。

一般情形：
a
i
b
i
（mod m）（i＝1,2,…,k），则
kk
（i）

a
i
i1
k

b
i
（mod m）
i1
k
i1
（ii）

a
i


b
i
（mod m）
i1

【推论1】a≡b （mod m）

na≡nb （mod m），其中n为正整数。
【推论2】a≡b （mod m）


a
n
b
n
（mod m），其中n为正整数。
【推论3】x≡y （mod m），
a
i
b
i
（mod m）（i＝1,2,…,k），
则
a
0
a
1
xa
2
xa
k
x
≡
b
0
b1
yb
2
yb
k
y
（mod m）




【例6】2003年5月9日是星期五，问此后的第2
2003
天是星期几？

2k2k

（解） 2
2003
＋5≡
2
6 672

3
667
2
2
＋5 (mod 7）
≡
12
＋5 (mod 7））
≡9 (mod 7）
≡2 (mod 7）

【例7】设十进制整数n＝
a
k
a
k 1

a
1
a
0
，则
3│n

3│
a
k
a
k1


a
1
a
0

9│n

9│
a
k
a
k1


a
1
a
0

（证）因
n＝
a
k
10
n＝
a
k
10
k< br>a
1
10a
0
≡
a
k
a
k1


a
1
a
0
(mod 3)
a
1
10a
0
≡
a
k
a
k1


a
1
a
0
(mod 9)
k

【例8】设整数n的1000进制表示式为
n＝
a
k
1000
k
则7（或11，或13）│n

7（或11，或13）│

a
0
a
2


－

a
1
a
3



（证）因
n＝
a
k
1000
k
 a
1
1000a
0

a
1
1000a
0

k1
k1
≡
a
k

1

a
k1

1

n≡
a
k

1

a
k 1

1

n≡
a
k

1

a
k1

1

k
k
k
< br>
a
1

1

a
0
mod 7


a
1

1

a
0
mod 11


a
1

 1

a
0
mod 13
k1
例如，判断n＝12345678能否被7(或11，或13)整除：
12345678＝12×1000
2
+345×1000+678
而 (12+678)－345＝345不能被7、11、13整除
故1234567不能被这3个数整除。

【例9】设十进制整数n＝
a< br>k
a
k1

a
1
a
0
，则
11│n

11│

a
0
a
2

－

a
1
a
3



2│n

2│
a
0

4│n

4│
a
1
a
0


4│
2a
1
a
0

8│n

8│
a
2
a
1
a
0


8│
4a
2
2a
1
a
0

2
│n


2
│
a
i1
< br>a
1
a
0

ii

例如，判断n＝981234576能否被11、2、4、8、16整除。
因为（6+5+3+1+9）－（7+4+2+8）＝3，故n不能被11整除
因2│6，故2│n
4├76或4├2×7+6＝22，故4├n
8│4×5+2×7+6＝40，故8│n
因8×4+4×5+10×7+6≡0 mod 16，故16│n

【性质5】消去律：设ad≡bd （mod m）。若（d，m）＝1，则
a≡b （mod m）。
（证）ad≡bd （mod m）

m│ad－ bd＝(a－b)d
而（d，m）＝1，故m│(a－b)，即 a≡b （mod m）

【例10】95≡25 (mod 7)，且（5，7）＝1，故19≡5(mod 7)

【反例11】115≡25 (mod 15)，即23×5≡5×5(mod 15)，但23≠5(mod 15)
因为（5，15）＝5＞1


【性质6】a≡b （mod m）且k＞0，则ak≡bk （mod mk）
（证）a≡b （mod m）

m│a－ b

mk│(a－b)k＝ak－bk

ak≡bk （mod mk）

【例12】19≡5 (mod 7)，k＝4＞0，所以76≡20 (mod 28)

【性质7】a≡b （mod m）且d│m，则
a≡b mod d
（证）a≡b （mod m）

m│a－b
又 d│m

d│a－b
即 a≡b mod d

另有一些性质，这里就不再一一列举，有兴趣的同学可参阅相关参考书。

2.2剩余类和完全剩余系
设m为正整数，记
C
a
＝
< br>ccZ,ac(modm)


C
a
非空，至少a∈
C
a

。

【定理2.2.1】设m是一个正整数，则
（i）
（ii）
任一整数必包含在某个
C
r
中，0≢r≢m－1
C
a
＝
C
b


a≡b （mod m）
a
（iii）
C


C
b
＝φ

a≠b （mod m）
【定义2.2.1】
C
a
叫做模m的a的剩余类。
一个剩余类中的任一个数叫做该类的剩余或代表。
若
r
0
,r1
,,r
m1
是m个整数，且其中任何两个都不在同一个剩余类中，则称r
0
,r
1
,,r
m1
为模m的一个完全剩余系。
【注】每个剩余类中都包含了无穷多个整数，而完全剩余系则恰好由m个数组
成。

模m的剩余类共有m个，例如
C
0
,

C
1
,,C
m1

【例13】设m＝10，则
C
a
＝

a10kkZ


是模m＝10的剩余类。

模10的完全剩余系举例：
（1）0，1，2，…，9
（2）1，2，3，…，10
（3）0，－1，－2，…，－9
（4）0，3，6，9，…，27
（5）10，11，22，33，44，…，99
（6）20，1，－18，13，64，－55，－94，－3，18，9

剩余类和完全剩余系的相关性质：
【定理2.2.2】整数
r
0
, r
1
,,r
m1
为m的一个完全剩余系

r
i
r
j
mod m。
其中（0≢i＜j≢m－1）
【例14】m的典型完全剩余系：
最小非负完全剩余系：0，1，…，m－1
最小正完全剩余系：1，2，…，m
最大非正完全剩余系：0，－1，…，－(m－1)
最大负完全剩余系：－1，－2，…，－m

【定理2.2.3】设a是满足(a， m)＝1的整数，b为任意整数。若x遍历模m的

一个完全剩余系，则ax＋b遍历模m 的一个完全剩余系。
（证）设
r
0
,r
1
,,r
m1
为m的一个完全剩余系。
由定理2.2.2知，
r
i
r
j
（mod m） （0≢i＜j≢m－1）
又(a，m)＝1，故
ar
i
ar
j
（mod m）
从而
ar
i
bar
j
b
（mod m）
由定 理2.2.2，
ar
0
b
，
ar
1
b
，…，
ar
m1
b
，是模m的一个完全剩余系。
【例15】（例3）设m＝10，原剩余系为0，1，…，9。
当a＝7，b＝5时，新的剩余系为：5，12，17，…，68
当a＝3，b＝6时，新的剩余系为：6，9，12，…，33


【定理2.2.4】设
m
1
,m
2
是 两个互素的正整数，若
x
1
,x
2
分别遍历
m
1< br>,m
2
的完全剩余系，则
m
2
x
1
m1
x
2
遍历模
m
1
m
2
的完全剩余系 。
x
2
分别遍历
m
1
,m
2
个整数时，
m
2
x
1
m
1
x
2
遍历
m
1
m
2
（证）当
x
1
,
个整数。 < br>问题转化为：证明
m
1
m
2
个整数
m
2x
1
m
1
x
2
模
m
1
m< br>2
两两不同余。
用反证法：若存在
x
1
,x
2和
y
1
,y
2
满足
m
2
x
1
m
1
x
2
≡
m
2
y
1
m
1
y
2
mod
m
1
m
2

则由2.1节性质7知
m
2
x
1
m
1
x
2
≡
m
2
y
1
m
1
y
2
mod
m
1

即
m
2
x
1
≡
m
2
y
1
mod
m
1

而（m
1
,m
2
）＝1，故由同余的性质知
x
1
≡
y
1
mod
m
1

同理可证，
x
2
≡
y
2
mod
m
2
。


【例16】设p、q是两个不同的素数，n＝ pq，则对任意整数c，存在唯一的一
对数x和y，满足
qx＋py＝c （mod n）， 0≢x＜p，0≢y＜q
（证）首先知p、q互素。
再由定理2.2.4，当 x、y分别遍历模p、q的完全剩余系时，qx＋py遍历模n
＝pq的完全剩余系。故存在唯一的一对 整数x、y，满足上式。

2.3简化剩余系和欧拉函数
【定义2 .3.1】（定义1）设n为正整数，则1,2,…,n中与n互素的整数的个
数，记作
(n)，叫做欧拉（Euler）函数。

【例17】（例1）设n＝10，则1,2,…,10中与10互素的数为
1,2,7,9，故

(10)＝4

【例18】
(1)＝1，

(2)＝1，

(3)＝2，

(4) ＝2，

(6)＝2，即1,2,…,6中与6互素的数为1，5

(2 0)＝8，即1,2,…,20中与20互素的数为1,3,7,9,11,13,17,19

欧拉函数的若干性质：
【性质1】设p为素数，则

(p)＝p－1。


1

【性质2】设p为素数，且整数α≣1，则
(
p
)＝
p


1



p



证明：（证）1,2,…,
p
中与p 不互素的数共有
p
p，2p，3p，4p，…，
p
由此即

(
p
)＝
p



1
个，这些数是

1
P


p

1
＝< br>p

1

p1

＝
p



1


1



。
p


【性质3】设整数n＝pq，其中p，q为不同的素数，则

(n)＝

(pq)＝

(p)

(q)＝(p －1)(q－1)
（证）设整数a满足1≢a≢n，若(a，n)＝d＞1，则必有
d
＝sp或d＝tq （因为n的因数只有1，p，q，pq＝n）
即必有 p│d或q│d，从而有p│a或q│a
这说明与n不互素的数a必为a＝sp或a＝tq.
这样的 a为
p，2p，3p，4p，…，(q－1)p，qp
和q，2q，3q，4q，…，(p－1)q，pq
共有p＋q－1个
∴

(n)＝

(pq)＝pq－(p＋q－1)＝(p－1)(q－1) ＝

(p)

(q)

【例19】

(143)＝

(11·13)＝

(11)

(13)＝10·12＝120

【性质4】设整数n＝
pq
，其中p，q为不同的素数，则




(n)＝

(
pq
)＝

(
p
)

(
q
)＝
n


1



1

1


1


p

q

证明：略
< br>【推论】设整数n有标准分解式
p
1
1
p
2
2

p
k
k
，则



(n)＝n

pn


1

1

1


1





11


1

1


＝
n



p
1

p
2


p
k

p



【例20】

(100)＝

1
22
(2·5)＝100

2 5

4
＝40

(360)＝



1
32
(2·3·5)＝360
24

＝96
235
【性质5】欧拉函数


n

是乘性函数（或称积 性函数）。即若正整数m，n互
素，则

(mn)＝

(m)

(n)。
（证）记m、n的标准分解式分别为

m
＝
p
1
1
p
2
2

p
k
k
，n＝
q
1
1
q
2
2

q
j< br>j

则

1

2

j

(mn)＝

p
1
p
2
p
k
k
q
1
1
q
2
2
q
j








1


1


1


1





1



1
＝
mn


1
p




< br>
1
p


q
1


q
j


1


k


 

1


1


1


1





1

1n1

1
＝
m



p
1

p
k

q
1

qj








＝< br>
(m)

(n)

【例21】设m＝33，n＝32，求

(33·32)。
（解）(33，32)＝1，故

(33·32)＝

(33)

(32)＝ 33

1
210
·32

＝160

3112

【定义2.3.2】一个模m的剩余类叫做简化剩余类（或互素 剩余类、既约剩余类、
不可约剩余类），如果该类中存在一个与m互素的剩余。
注：本定义与剩余的选取无关。
比如：对于 m=20而言，
C
3
，
C
7
都是20的简化剩余类，
C
15
却不是


【定理2.3.1】设
r
1
、
r
2
是同 一剩余类中的两个剩余，则
r
1
与m互素的充分必
要条件是
r
2
与m互素。
（证）由题设知
r
1
＝
r
2
＋km
再由最大公因子性质知（r
1
，m）＝（
r
2
，m）
∴ （
r
1
，m）＝1

（
r
2
，m）＝1

【定义2.3.3】设m为正整数，在模m的所有不同简化剩余类中，从每个类任取
一个数组成的整数集合，叫做模m的一个简化剩余系（或称为缩系、互素剩余
系、既约剩余系、不可约剩 余系）。
【例22】模6的简化剩余系为1，5
模20的简化剩余系为1,3,7,9,11,13,17,19

【定理2.3.2】m的简化剩余系的元素个数为


m


【例23】素数p的简化剩余系为 1，2，……，p－1，即


p

＝p－1

【定理2.3.3】设整数
r
1
，
r
2
，…，
r


m

均与m互素，且两两模m不同余，则
它们构成模m的一个简化剩余系。

【定理2.3.4】设整数
r
1
，
r
2
，…，
r


m

均与m互素，若它们构成模m的一个简化剩余系，则这些
r
i
必两两模m不同余。

（证）由 题意知
r
1
，
r
2
，…，
r


m

是来自模m的不同简化剩余类的剩余，而不
同剩余类中的数必互不同余。

【推论】设整数
r
1
，
r
2
，…，r


m

均与m互素，则它们构成模m的简化剩余系
的充分必要条件是这些
r
i
两两模m不同余。

【定理2.3.5 】设m为正整数，a是满足(a，m)＝1的整数。那么，若x遍历模
m的一个简化剩余系，则ax也遍 历模m的一个简化剩余系。
（证）首先，由(a，m)＝1及(x，m)＝1知(ax，m)＝1，即 ax是简化剩余类的
剩余。其次，若
x
1
x
2
（mod m），则必有
ax
1
ax
2
（mod m）（否则，
由
ax
1
ax
2
（mod m）及(a，m)＝1可得
x
1
x
2
（mod m），矛盾）
因此x遍历模m的一个简化剩余系时，ax遍历


m

个 数，且它们两两m不同余。
由定理2.3.3知ax也遍历模m的一个简化剩余系。

【例24】（例7）已知1，7，11，13，17，19，23，29是模30的简化剩余系，
(7 ，30)＝1，则7，49，77，91，119，133，161，203也是模30的简化剩余系。


【定理2.3.6】设m为正整数，a是满足(a，m)＝1的整数。则存在整数
a

（1≢
a

＜m）使得
aa

≡1 （mod m）
（证）（构造性证明）由(a，m)＝1知存在整数s，t，使得
sa＋tm＝(a，m)＝1
即
sa－1＝(－t)m
因此，所求
a

＝s。
【例25】设m＝737，a＝635，求
a

，满足
aa＇≡1 （mod m）
（解）利用广义欧几里得除法，可找到s＝－224，t＝193，使得
(－224) ·635＋193·737＝1
∴ a＇≡－224≡513 （mod 737）
即 635·(－224) ≡1 （mod 737）

【定义2.3.4】将定理2.3.7中满足条件的< br>a

叫作a（对模m）的逆，记为
a
即
aa
1
≡1 mod m

实质上，a与
a
1
1
。
互为逆元素。

【例26】对任何模数m＞1而言，至少有两个数有逆。即
1
≡1，

m1

1
1
≡m－1（mod m）
（或

1

≡－1）

关于模逆元的性质：
【性质1】若a模m可逆，则（a，m）=1。
（证）a可逆，则a的逆
a
1
1
存在，且满足
1
a
a
即存在整数k，使得a
a
1
≡1 （mod m）
=1＋km= km＋1
1
再由最大公因子的性质知（a
a
1
，m）=（m，1）=1
1
而 （a
a
，m）=1

（a，m）=1且（
a
，m）=1
【推论】a模m可逆的充分必要条件是（a，m）=1。

【性质2】
a
意整数。
1
不唯一。即若
a
1
存在，则
a
1
＋km都是a的逆，其中k为任
（证）只需直接验证 ：已知
a
1
是a的逆，即
≡1 （mod m）
a
a
那么，对任意整数k，有
a(
a
1
1
＋km) ≡a
a
1
＋ akm≡a
a
1
＋0≡1 （mod m）

【例27】m＝7，a＝2，直接计算有
……，
2·(－3)≡1 （mod 7）
2·4≡1 （mod 7）

2·11≡1 （mod 7）
2·18≡1 （mod 7）
……
即对模7而言，整数4＋7k都是2的逆（k∈z）

【性质3】若b和c都是a的逆，则有b≡c （mod m）。
（证）已知ab≡1 （mod m）， ac≡1 （mod m）
从而 ab≡ac （mod m）
而(a,m)＝1，故由消去律知 b≡c （mod m）。

【推论1】设整数a有逆
a
1
，则整数b是a的逆的充分必要条件是
1
b≡
a
即b＝
a
1
（mod m）。
+km（k∈z）。
1
（证）只要验证当b≡
a
（mod m）时，b也是a的逆即可。显然。
反之，20≠17 mod 50，则20不是3的逆。

【推论2】在模m的一个简化剩余系中，a的逆
a
1
是唯一的。
1
【例28】m＝7，选模7的最小正简化剩余系{1，2，…，6}，则a＝2的逆
2
4且唯一。
[性质4】（1）
a
＝

1
1
≡a。 （2）

a
1
a
2
a
k
（证）直接 验证即可。

【推论】
a

1
≡
a
1
1
a
2
1
a
k
1


n
1
≡
a

1

n
。

【例】设m＝55，求8和24模55的逆。
（解）首先可以观察出2模55的逆为
2
所以
8
1
1
＝28
≡
2

3
1
≡
2

1

3
≡
28
≡7 mod 55
3

24
1
≡
23
1

3

1
≡
2

1
33
1
≡
2

3
1
3
1≡
28
·37≡39
3

计算
a
的方法
【方法1】利用简化剩余类的性质枚举求逆
例 m＝11，a＝5，则
5·1≡5， 5·2≡10， 5·3≡4， 5·5≡3，
5·6≡8， 5·9≡1
∴
5
＝9 mod 11
【方法2】利用辗转相除法
【方法3】利用欧拉函数和欧拉定理的结论

2.4欧拉定理与费马小定理
【定理2.4.1】（Euler定理）设m是大于1的整数，若整数a满足(a，m)＝1，
则有
1
a
≡1 （mod m）
（证）设
r
1
, r
2
,

,r


m

为m的最 小正简化剩余系，则当(a，m)＝1时，


m

ar
1
,ar
2
,

,ar


m


也为模m的一个简化剩余系。故
ar
1
,ar
2
,

,ar


m

是模m的最小正剩余
r
1
,r
2
,

,r


m
的某个排列。所以
ar
1
ar
2

ar


m

≡
r
1
r
2

r


m

（mod m）
即
a


m



m


r r
12

r


m


≡
r
1
r
2

r


m

（mod m）
又由(
r
i
，m)＝1知，(
r
1
r
2

r


m

，m)＝1， 故有
a
≡1 （mod m）
【定理2.4.2】（Fermat定理）（定理2）设p为素数，a为任意正整数，则
a
≡a （mod p）
（证）(1)
pa
，则有
a
≡0 （mod p）


a
≡0 （mod p）
即
a
≡a （mod p）
(2) p├a，必有(a,p)＝1，由定理2.4.1
p1
p
p
p
a
≡1 （mod p）

两边同乘以a，得
a
≡a （mod p）

【例】设p＝11，a＝2，则

(11)＝10，故
p
2
≡2 mod 11
设p＝23，a＝10，则

(23)＝22，故
11
10
23
≡10 mod 23

【推论】设m＞1，则m为素数的必要条件是：对某个m├a的整数a，有
a
m1
≡1 （mod m）
应用：用于否定一个整数为素数。
意义：是判断一个正整数为素数的概率算法的理论基础