三年级上册数学题-玫瑰花语大全

第三章 同 余
§1 同余的概念及其基本性质
定义1设mZ

，称之为模。若用m去除两个整数a与b所得的余数相同，
则称a,b对模m同余，记作：a b(modm)；若所得的余数不同，则称a,b对模m
不同余，记作：a

b( modm)。
例如，81(mod7)，；所有偶数a0(mod2)，所有奇数a1(mod2 )。
同余是整数之间的一种关系，它具有下列性质：
1、aa(modm)；（反身性）2、若ab(modm)，则ba(modm)；（对称性）

3、若ab(mod m)，bc(modm)，则ac(modm)；（传递性）
故同余关系是等价关系。
定理 1整数a,b对模m同余的充分必要条件是m|(ab)，即abmt，
tZ。
证明设 amq
1
r
1
，bmq
2
r
2
， 0r
1
,r
2
m，
则ab(modm)r
1
r
2
abm(q
1
q
2
)m|(ab)。
性质1(1)若a
1
b
1
(modm)，a
2
 b
2
(modm)，则a
1
a
2
b
1
b
2
(modm)；

(2)若abc(modm)，则acb(modm)。

性质2若a
1
b
1
(modm)，a
2
b
2
(modm )，则a
1
a
2
b
1
b
2
(modm) ；

特别地，若ab(modm)，则kakb(modm)。
定理2若A

1


k
B

1

k
(modm)，x
i
y
i
(modm)，i1,2,, k，
则

1


k

A

1


k

k

1
x
1
x
k


1


k

B
1


k

k

1
y1
y
k
(modm)；特别地，若a
i
b
i
(modm)，
i0,1,2,,n，则a
n
x
n
a
n1
x
n1
a
0
b
n
x
n
b
n1
x
n1
b
0
(modm)。< br>性质3若aa
1
d，bb
1
d，(d,m)1，ab(mod m)，则a
1
b
1
(modm)。

性质 4(1)若ab(modm)，k0，则akbk(modmk)；
abm

( 2)若ab(modm)，d是a,b及m的任一公因数，则(mod)。
ddd
性质5若 ab(modm
i
)，i1,2,,k，则ab(mod[m
1
,m
2
,,m
k
])。

反之亦然。

性质 6若ab(modm)，d|m，d0，则ab(modd)。
性质7若ab(modm)，则 (a,m)(b,m)，因而若d能整除a,b及m两数
之一，则d必能整除a,b中的另一数。
例1求3
406
写成十进位数时的个位数码。
解事实上，只需求满足3
406
a(mod10)，0a9的数a。
因为391(mod10)， 所以3
即个位数码是9。
例2证明：当n为奇数时，3|2
n
1，当n为偶 数时，3

|2
n
1。
证明因为
n
2406(3)
2203
(1)
203

19(mod10 )，
21(mod3)，所以2
n
1(1)
n
1(mo d3)，
nn
当n为奇数时，21(1)1110(mod3)，故3|2 1，
当n为偶数时，2
n
1(1)
n
1112(mo d3)，故3

|2
n
1。

同余性质在算术中的一些应用。
一、检查因数的方法
1、一整数能被3（或9）整除的充分必要条件是它的十进位数码之和能被
3（或9）整除。
证明 只需讨论正整数即可。任取
a
Z

，则a可以写成十进位的形式：

aa
n
10
n
a
n1
10
n1
a
0
，0a
i
10，于是，由101(mod3 )可知
aa
n
a
n1
a
0
(mod3 )，从而3|a3|a
n
a
n1
a
0
。
对于9同理可证。

2、设正整数
aa
n
1000
n< br>a
n1
1000
n1
a
0
，0ai
1000
，则7（或
11或13）|a的充分必要条件是7（或11或13） |
(a
0
a
2
)(a
1
a
3< br>)。

证明 因为7×11×13=1001。
例3 a=5874192能被3和9整除。
例4 a=435693能被3整除，但不能被9整除。
例5 a=637693能被7整除；a=能被13整除。
二、弃九法（验算整数计算结果的方法）
例6 设a=28997，b=39495，P=ab=15，检查计算是否正确。
解 令
a a
n
10
n
a
n1
10
n1
 a
0
，0a
i
10

bb
m
10< br>m
b
m1
10
m1
b
0
，0 b
j
10

Pc
l
10
l
c
l1
10
l1
c
0
，0c
k
10

则
(

a
i
)(

b
j
)

c
k
(mod9)
（*）
i0j0k0
nml
若（*）不成立，则P≠ab，故在本题中，计算不正确。
注 (1) 若（*）不成立，则计算不正确；但否命题不成立。
(2) 利用同样的方法可以用来验证整数的加、减运算的正确性。

§2 剩余类及完全剩余系
定理1设m0，则全体整数可分成m个集合，记 作：K
0
,K
1
,,K
m1
，其
中K
r
{qmr|qZ}，r0,1,,m1，这些集合具有下列性质：
(1)每个整 数必包含在而且仅在上述的一个集合中；
(2)两个整数同在一个集合的充分必要条件是对模m同余。< br>证(1)设a是任一整数，则必有amqr
a
，0r
a
m，< br>于是由r
a
的存在性可知aK
r
a
，由r
a
的唯一性可知a只能在K
r
a
中。
(2)设整数a,bK
r，则amq
1
r，bmq
2
r，故ab(modm)。
反之，若ab(modm)，则a,b必处于同一K
r
中。

定义1定理 1中的K
0
,K
1
,,K
m1
称为模m的剩余类，一个 剩余类中的任一
数称为它同类数的剩余。
若m个整数a
0
,a
1,,a
m1
中任何两个数都不在同一剩余类，则a
0
,a
1
,,a
m1
称为模m的一个完全剩余系。
推论 m个整数作成模m的一个完全剩余系的充分必要条件是它们对模m
两两不同余。
例如，下列序列都是模m的完全剩余系：
(1)0,1,2,,m1；（最小非负完全剩 余系）
(2)0,m1,,ama,,(m1)m(m1)；
(3)0,m 1,,(1)
a
ma,,(1)
m1
m(m1)；
(4)当m为偶数时，1


2


当m为奇数时，mmm
,1,,1,0,1,,1；
222
mmm
1, ,1,0,1,,1,；
222

m1m1
,,1,0,1, ,。（绝对最小完全剩余系）
22

定理2设mZ

，(a ,m)1，bZ，若x通过模m的一个完全剩余系，则
axb也通过模m的一个完全剩余系，即若 a
0
,a
1
,,a
m1
是模m的完全剩余系，
则aa
0
b,aa
1
b,,aa
m1
b也是模m 的完全剩余系。

证只需证明aa
0
b,aa
1
b, ,aa
m1
b两两不同余即可，采用反证法。
设aa
i
ba a
j
b(modm)(ij)，则aa
i
aa
j
(m odm)，
又(a,m)1，于是a
i
a
j
(modm)(i j)，与已知矛盾，
故aa
0
b,aa
1
b,,aa
m1
b也是模m的完全剩余系。
定理3设m
1
,m
2
 Z

，(m
1
,m
2
)1，而x
1
,x
2
分别通过模m
1
,m
2
的完全剩
余系，则m2
x
1
m
1
x
2
也通过模m
1m
2
的完全剩余系。
证因为x
1
,x
2
分别通 过m
1
,m
2
个整数，所以m
2
x
1
m
1
x
2
通过m
1
m
2
个整数，
下 证这m
1
m
2
个整数对模m
1
m
2
两两不 同余。
设m
2
x
1
'm
1
x
2
'm
2
x
1
''m
1
x
2
''(mo dm
1
m
2
)，其中x
1
',x
1
'', x
2
',x
2
''分别是x
1
,x
2
所< br>通过的完全剩余系中的数，则m
2
x
1
'm
2
x< br>1
''(modm
1
)，m
1
x
2
'm< br>1
x
2
''(modm
2
)，
又(m
1,m
2
)1，故x
1
'x
1
''(modm
1
)，x
2
'x
2
''(modm
2
)，这说 明m
2
x
1
m
1
x
2
所通过的数两两不 同余，因此，m
2
x
1
m
1
x
2
也通过 模m
1
m
2
的完全剩余系。
例1设m0(mod2)，a
1
,,a
m
及b
1
,,b
m
都是模m的完全剩 余系，则
a
1
b
1
,,a
m
b
m< br>不是模m的完全剩余系。
证：因为a
1
,,a
m
及b
1
,,b
m
都是模m的完全剩余系，
m
m(m1)
m m
所以

a
i


i(modm)，同理
b
i
(modm)，
222
i1i1i1
m m
从而

(a
i
b
i
)

a
i


b
i

i1i1i1
mmm
mm
0(modm)，
22
m
若a
1
b1
,,a
m
b
m
是模m的完全剩余系，则

(a
i
b
i
)
i1
m
(modm)，矛盾 。
2
因此，a
1
b
1
,,a
m
b< br>m
不是模m的完全剩余系。

例2证明：对任何正整数n，存在着仅有数字 1,0组成的数a，使得n|a。

证：考察n1个数：1,11,,11
 
1，它们对模n至少有两个在同一同余类中，
n1个1
设bc，b11 

0a。

1，c11

1，bc(mo dn)，则n|(bc)11

100

k个1s个1ks个1
s个0
例3设mZ

，(a,m)1，bZ，x通过模m的一个完全剩 余系，
则



x

axb

1

(m1)。
m

2
因为x通过模m的一个完全剩余 系，所以axb通过模m的一个完全

证
01m1

axb< br>
剩余系，从而

，

通过,,,
mmmm

故



x
m11

axb< br>
01
(m1)。


m

m mm2

§3 简化剩余系与欧拉函数
定义1欧拉函数< br>
(a)是定义在正整数集上的函数，它的值等于序列0,1,2,
,a1中与a互 质的数的个数。
注若a是质数，则

(a)a1；若a是合数，则
(a)a1。
定义2如果一个模m的剩余类中的数与m互质，则称它为一个与模m互质
的剩余类。
在与模m互质的全部剩余类中，从每一类各取一数所作成的数的集合称为
模m的一个 简化剩余系。


定理1模m的剩余类与模m互质的充分必要条件是此类中有一数与m 互质。
因此，与模m互质的剩余类的个数为

(m)，模m的每一简化剩余系是由与m 互质
的

(m)个对模m不同余的整数组成的。
证设K
0
, K
1
,,K
m1
是模m的全部剩余类，若K
r
与模m互 质，则(r,m)1；
反之，若有k
r
K
r
，(k
r< br>,m)1，则对于K
r
中任一数k
r
'qmk
r
，有(k
r
',m)1，
即K
r
与模m互质。
定理2若 a
1
,a
2
,,a

(m)
是

(m)个与m互质的整数，并且两两对模m不同余，
则a
1
,a
2
,,a

(m)
是模m的一个简化剩余系。
定理3若(a,m)1，x通 过模m的简化剩余系，则ax也通过模m的简化剩
余系。
证ax通过

(m) 个整数，而且由(a,m)1，(x,m)1可知(ax,m)1，
若ax
i
 ax
j
(modm)(ij)，则x
i
x
j
(modm )(ij)，与已知矛盾，
故ax通过模m的简化剩余系。

定理4设m
1
,m
2
Z

，(m
1
,m
2
) 1，而x
1
,x
2
分别通过模m
1
,m
2
的简化剩
余系，则m
2
x
1
m
1
x
2
也通过模m
1
m
2
的简化剩余系。

证由上一节定理3可知，若x
1
,x
2
分别通过模m
1
, m
2
的完全剩余系，则
m
2
x
1
m
1< br>x
2
也通过模m
1
m
2
的完全剩余系。下证当x1
,x
2
分别通过模m
1
,m
2
的简
化剩余系时，m
2
x
1
m
1
x
2
通过模 m
1
m
2
的一个完全剩余系中一切与m
1
m
2互质的
整数。
一方面，由(x
1
,m
1
)(x
2
,m
2
)(m
1
,m
2
)1可知(m2
x
1
,m
1
)1，(m
1
x
2< br>,m
2
)1，
于是(m
2
x
1
m
1
x
2
,m
1
)1，(m
1
x
2m
2
x
1
,m
2
)1，从而(m
2
x
1
m
1
x
2
,m
1
m
2< br>)1，
另一方面，由(m
2
x
1
m
1
x
2
,m
1
m
2
)1可知(m
2
x
1
m
1
x
2
,m
1
)(m
1
x
2
m
2
x
1
,m
2
)1，
于是(m
2
x
1
,m
1
)(m
1
x< br>2
,m
2
)1，从而(x
1
,m
1
)( x
2
,m
2
)1。
推论设m
1
,m
2< br>Z

，(m
1
,m
2
)1，则

(m
1
m
2
)

(m
1
)

(m
2
)。
证由定理4可知，若x
1
,x
2
分别通过模m
1
,m
2
的简化剩余系，则m
2
x
1
m
1
x
2
通过模m
1
m
2
的 简化剩余系，即m
2
x
1
m
1
x
2
通过

(m
1
m
2
)个整数。
另一方面，由于x
1
通过

(m
1
)个整数，x
2
通过

(m
2
)个整数，因此，m
2
x
1
m
1
x
2
通过

(m
1
)

(m2
)个整数。故

(m
1
m
2
)

(m
1
)

(m
2
)。

1
1


1


k

1< br>
2

。

定理5设ap
1
p2
p
k
，则

(a)a

111


p
1

p
2

< br>p
k



证先证

(p

)p

p

1
。在模p

的完全剩余系1 ,2,,p

中，与p

不互质
的数为p,2p,,p

1
p，共有p

1
个，故

(p

)p

p

1
。

k
< br>k

k
1

1

2

1

1
1

1

2
1
因此，< br>
(a)

(p
1
)

(p
2< br>)

(p
k
)(p
1
p
1
) (p
2
p
2
)(p
k
p
k
)

1

1


1


。< br>
a

111


p
1

p
2


p
k




§4 欧拉定理·费马定理
定理1(Euler)设mZ，m1，(a,m)1，则a

(m)
 1(modm)。
证设r
1
,r
2
,,r

(m )
是模m的简化剩余系，则ar
1
,ar
2
,,ar
< br>(m)
也是模m的简
化剩余系，于是(ar
1
)(ar
2)(ar

(m)
)r
1
r
2
r

(m)
(modm)，
即a

(m)
(r
1< br>r
2
r

(m)
)r
1
r
2< br>r

(m)
(modm)，又(r
1
,m)(r
2
,m)(r

(m)
,m)1，
故(r
1
r
2
r

(m)
,m)1，从而a

(m)< br>1(modm)。
推论(Fermat定理)若p是质数，则a
p
a(mo dp)。
证若(a,p)1，则由定理1可知a
p1
1(modp)，从而a< br>p
a(modp)。

若(a,p)1，则p|a，故a
p
a(modp)。
例1设p是奇质数，证明：
(1)1
p1
2
p1
(p1)
p1
1(modp)；
(2)1
p
2
p
(p1)
p
0(modp)；
mmm(3)若2
m


1(modp)，则12(p1)0(m odp)。
证(1)由费马定理可知i
p1
1(modp)，i1,2,,p 1，
故1
p1
2
p1
(p1)
p1111p11(modp)。
(2)由费马定理可知i
p
i (modp)，i1,2,,p1，
故1
p
2
p
(p 1)
p
12(p1)
p(p1)
0(modp)。2
(3)因为1,2,,p1是模p的简化剩余系，所以2,4,,2(p1)也是模p的 简化
剩余系，于是
1
m
2
m
(p1)
m
2
m
2
m
2
m
2
m
( p1)
m
2
m
[1
m
2
m
( p1)
m
](modp)，
mmm
又2
m

< br>1(modp)，故12(p1)0(modp)。

例2设p是除2 与5外的任一质数，kZ

，证明：p|99

9。

k(p1)个
证因为p2,5，所以(10
k
,p)1，
由费马定理 可知(10
k
)
p1
1(modp)，故
k(p1)个

p|(10
k
)
p1
199

9。< br>

第三章 同 余
§1 同余的概念及其基本性质
定义1设mZ

，称之为模。若用m去除两个整数a与b 所得的余数相同，
则称a,b对模m同余，记作：ab(modm)；若所得的余数不同，则称a,b 对模m
不同余，记作：a

b(modm)。
例如，81(mod7)， ；所有偶数a0(mod2)，所有奇数a1(mod2)。
同余是整数之间的一种关系，它具有下 列性质：
1、aa(modm)；（反身性）
2、若ab(modm)，则ba(mod m)；（对称性）

3、若ab(modm)，bc(modm)，则ac(modm) ；（传递性）
故同余关系是等价关系。
定理1整数a,b对模m同余的充分必要条件是m|(a b)，即abmt，
tZ。
证明设amq
1
r
1
，bmq
2
r
2
，0r
1
,r
2
m，
则ab(modm)r
1
r
2
abm(q
1
q
2
)m|(ab)。
性质1(1)若a
1
b
1
(modm)，a
2
b
2
(modm)，则a
1
a
2
b
1
b
2
(modm)；

(2)若abc(modm)，则acb(modm)。

性质2若a
1
b
1
(modm)，a
2
b
2
(modm )，则a
1
a
2
b
1
b
2
(modm) ；

特别地，若ab(modm)，则kakb(modm)。
定理2若A

1


k
B

1

k
(modm)，x
i
y
i
(modm)，i1,2,, k，
则

1


k

A

1


k

k

1
x
1
x
k


1


k

B
1


k

k

1
y1
y
k
(modm)；特别地，若a
i
b
i
(modm)，
i0,1,2,,n，则a
n
x
n
a
n1
x
n1
a
0
b
n
x
n
b
n1
x
n1
b
0
(modm)。< br>性质3若aa
1
d，bb
1
d，(d,m)1，ab(mod m)，则a
1
b
1
(modm)。

性质 4(1)若ab(modm)，k0，则akbk(modmk)；
abm

( 2)若ab(modm)，d是a,b及m的任一公因数，则(mod)。
ddd
性质5若 ab(modm
i
)，i1,2,,k，则ab(mod[m
1
,m
2
,,m
k
])。

反之亦然。

性质 6若ab(modm)，d|m，d0，则ab(modd)。
性质7若ab(modm)，则 (a,m)(b,m)，因而若d能整除a,b及m两数
之一，则d必能整除a,b中的另一数。
例1求3
406
写成十进位数时的个位数码。
解事实上，只需求满足3
406
a(mod10)，0a9的数a。
因为391(mod10)， 所以3
即个位数码是9。
例2证明：当n为奇数时，3|2
n
1，当n为偶 数时，3

|2
n
1。
证明因为
n
2406(3)
2203
(1)
203

19(mod10 )，
21(mod3)，所以2
n
1(1)
n
1(mo d3)，
nn
当n为奇数时，21(1)1110(mod3)，故3|2 1，
当n为偶数时，2
n
1(1)
n
1112(mo d3)，故3

|2
n
1。

同余性质在算术中的一些应用。
一、检查因数的方法
1、一整数能被3（或9）整除的充分必要条件是它的十进位数码之和能被
3（或9）整除。
证明 只需讨论正整数即可。任取
a
Z

，则a可以写成十进位的形式：

aa
n
10
n
a
n1
10
n1
a
0
，0a
i
10，于是，由101(mod3 )可知
aa
n
a
n1
a
0
(mod3 )，从而3|a3|a
n
a
n1
a
0
。
对于9同理可证。

2、设正整数
aa
n
1000
n< br>a
n1
1000
n1
a
0
，0ai
1000
，则7（或
11或13）|a的充分必要条件是7（或11或13） |
(a
0
a
2
)(a
1
a
3< br>)。

证明 因为7×11×13=1001。
例3 a=5874192能被3和9整除。
例4 a=435693能被3整除，但不能被9整除。
例5 a=637693能被7整除；a=能被13整除。
二、弃九法（验算整数计算结果的方法）
例6 设a=28997，b=39495，P=ab=15，检查计算是否正确。
解 令
a a
n
10
n
a
n1
10
n1
 a
0
，0a
i
10

bb
m
10< br>m
b
m1
10
m1
b
0
，0 b
j
10

Pc
l
10
l
c
l1
10
l1
c
0
，0c
k
10

则
(

a
i
)(

b
j
)

c
k
(mod9)
（*）
i0j0k0
nml
若（*）不成立，则P≠ab，故在本题中，计算不正确。
注 (1) 若（*）不成立，则计算不正确；但否命题不成立。
(2) 利用同样的方法可以用来验证整数的加、减运算的正确性。

§2 剩余类及完全剩余系
定理1设m0，则全体整数可分成m个集合，记 作：K
0
,K
1
,,K
m1
，其
中K
r
{qmr|qZ}，r0,1,,m1，这些集合具有下列性质：
(1)每个整 数必包含在而且仅在上述的一个集合中；
(2)两个整数同在一个集合的充分必要条件是对模m同余。< br>证(1)设a是任一整数，则必有amqr
a
，0r
a
m，< br>于是由r
a
的存在性可知aK
r
a
，由r
a
的唯一性可知a只能在K
r
a
中。
(2)设整数a,bK
r，则amq
1
r，bmq
2
r，故ab(modm)。
反之，若ab(modm)，则a,b必处于同一K
r
中。

定义1定理 1中的K
0
,K
1
,,K
m1
称为模m的剩余类，一个 剩余类中的任一
数称为它同类数的剩余。
若m个整数a
0
,a
1,,a
m1
中任何两个数都不在同一剩余类，则a
0
,a
1
,,a
m1
称为模m的一个完全剩余系。
推论 m个整数作成模m的一个完全剩余系的充分必要条件是它们对模m
两两不同余。
例如，下列序列都是模m的完全剩余系：
(1)0,1,2,,m1；（最小非负完全剩 余系）
(2)0,m1,,ama,,(m1)m(m1)；
(3)0,m 1,,(1)
a
ma,,(1)
m1
m(m1)；
(4)当m为偶数时，1


2


当m为奇数时，mmm
,1,,1,0,1,,1；
222
mmm
1, ,1,0,1,,1,；
222

m1m1
,,1,0,1, ,。（绝对最小完全剩余系）
22

定理2设mZ

，(a ,m)1，bZ，若x通过模m的一个完全剩余系，则
axb也通过模m的一个完全剩余系，即若 a
0
,a
1
,,a
m1
是模m的完全剩余系，
则aa
0
b,aa
1
b,,aa
m1
b也是模m 的完全剩余系。

证只需证明aa
0
b,aa
1
b, ,aa
m1
b两两不同余即可，采用反证法。
设aa
i
ba a
j
b(modm)(ij)，则aa
i
aa
j
(m odm)，
又(a,m)1，于是a
i
a
j
(modm)(i j)，与已知矛盾，
故aa
0
b,aa
1
b,,aa
m1
b也是模m的完全剩余系。
定理3设m
1
,m
2
 Z

，(m
1
,m
2
)1，而x
1
,x
2
分别通过模m
1
,m
2
的完全剩
余系，则m2
x
1
m
1
x
2
也通过模m
1m
2
的完全剩余系。
证因为x
1
,x
2
分别通 过m
1
,m
2
个整数，所以m
2
x
1
m
1
x
2
通过m
1
m
2
个整数，
下 证这m
1
m
2
个整数对模m
1
m
2
两两不 同余。
设m
2
x
1
'm
1
x
2
'm
2
x
1
''m
1
x
2
''(mo dm
1
m
2
)，其中x
1
',x
1
'', x
2
',x
2
''分别是x
1
,x
2
所< br>通过的完全剩余系中的数，则m
2
x
1
'm
2
x< br>1
''(modm
1
)，m
1
x
2
'm< br>1
x
2
''(modm
2
)，
又(m
1,m
2
)1，故x
1
'x
1
''(modm
1
)，x
2
'x
2
''(modm
2
)，这说 明m
2
x
1
m
1
x
2
所通过的数两两不 同余，因此，m
2
x
1
m
1
x
2
也通过 模m
1
m
2
的完全剩余系。
例1设m0(mod2)，a
1
,,a
m
及b
1
,,b
m
都是模m的完全剩 余系，则
a
1
b
1
,,a
m
b
m< br>不是模m的完全剩余系。
证：因为a
1
,,a
m
及b
1
,,b
m
都是模m的完全剩余系，
m
m(m1)
m m
所以

a
i


i(modm)，同理
b
i
(modm)，
222
i1i1i1
m m
从而

(a
i
b
i
)

a
i


b
i

i1i1i1
mmm
mm
0(modm)，
22
m
若a
1
b1
,,a
m
b
m
是模m的完全剩余系，则

(a
i
b
i
)
i1
m
(modm)，矛盾 。
2
因此，a
1
b
1
,,a
m
b< br>m
不是模m的完全剩余系。

例2证明：对任何正整数n，存在着仅有数字 1,0组成的数a，使得n|a。

证：考察n1个数：1,11,,11
 
1，它们对模n至少有两个在同一同余类中，
n1个1
设bc，b11 

0a。

1，c11

1，bc(mo dn)，则n|(bc)11

100

k个1s个1ks个1
s个0
例3设mZ

，(a,m)1，bZ，x通过模m的一个完全剩 余系，
则



x

axb

1

(m1)。
m

2
因为x通过模m的一个完全剩余 系，所以axb通过模m的一个完全

证
01m1

axb< br>
剩余系，从而

，

通过,,,
mmmm

故



x
m11

axb< br>
01
(m1)。


m

m mm2

§3 简化剩余系与欧拉函数
定义1欧拉函数< br>
(a)是定义在正整数集上的函数，它的值等于序列0,1,2,
,a1中与a互 质的数的个数。
注若a是质数，则

(a)a1；若a是合数，则
(a)a1。
定义2如果一个模m的剩余类中的数与m互质，则称它为一个与模m互质
的剩余类。
在与模m互质的全部剩余类中，从每一类各取一数所作成的数的集合称为
模m的一个 简化剩余系。


定理1模m的剩余类与模m互质的充分必要条件是此类中有一数与m 互质。
因此，与模m互质的剩余类的个数为

(m)，模m的每一简化剩余系是由与m 互质
的

(m)个对模m不同余的整数组成的。
证设K
0
, K
1
,,K
m1
是模m的全部剩余类，若K
r
与模m互 质，则(r,m)1；
反之，若有k
r
K
r
，(k
r< br>,m)1，则对于K
r
中任一数k
r
'qmk
r
，有(k
r
',m)1，
即K
r
与模m互质。
定理2若 a
1
,a
2
,,a

(m)
是

(m)个与m互质的整数，并且两两对模m不同余，
则a
1
,a
2
,,a

(m)
是模m的一个简化剩余系。
定理3若(a,m)1，x通 过模m的简化剩余系，则ax也通过模m的简化剩
余系。
证ax通过

(m) 个整数，而且由(a,m)1，(x,m)1可知(ax,m)1，
若ax
i
 ax
j
(modm)(ij)，则x
i
x
j
(modm )(ij)，与已知矛盾，
故ax通过模m的简化剩余系。

定理4设m
1
,m
2
Z

，(m
1
,m
2
) 1，而x
1
,x
2
分别通过模m
1
,m
2
的简化剩
余系，则m
2
x
1
m
1
x
2
也通过模m
1
m
2
的简化剩余系。

证由上一节定理3可知，若x
1
,x
2
分别通过模m
1
, m
2
的完全剩余系，则
m
2
x
1
m
1< br>x
2
也通过模m
1
m
2
的完全剩余系。下证当x1
,x
2
分别通过模m
1
,m
2
的简
化剩余系时，m
2
x
1
m
1
x
2
通过模 m
1
m
2
的一个完全剩余系中一切与m
1
m
2互质的
整数。
一方面，由(x
1
,m
1
)(x
2
,m
2
)(m
1
,m
2
)1可知(m2
x
1
,m
1
)1，(m
1
x
2< br>,m
2
)1，
于是(m
2
x
1
m
1
x
2
,m
1
)1，(m
1
x
2m
2
x
1
,m
2
)1，从而(m
2
x
1
m
1
x
2
,m
1
m
2< br>)1，
另一方面，由(m
2
x
1
m
1
x
2
,m
1
m
2
)1可知(m
2
x
1
m
1
x
2
,m
1
)(m
1
x
2
m
2
x
1
,m
2
)1，
于是(m
2
x
1
,m
1
)(m
1
x< br>2
,m
2
)1，从而(x
1
,m
1
)( x
2
,m
2
)1。
推论设m
1
,m
2< br>Z

，(m
1
,m
2
)1，则

(m
1
m
2
)

(m
1
)

(m
2
)。
证由定理4可知，若x
1
,x
2
分别通过模m
1
,m
2
的简化剩余系，则m
2
x
1
m
1
x
2
通过模m
1
m
2
的 简化剩余系，即m
2
x
1
m
1
x
2
通过

(m
1
m
2
)个整数。
另一方面，由于x
1
通过

(m
1
)个整数，x
2
通过

(m
2
)个整数，因此，m
2
x
1
m
1
x
2
通过

(m
1
)

(m2
)个整数。故

(m
1
m
2
)

(m
1
)

(m
2
)。

1
1


1


k

1< br>
2

。

定理5设ap
1
p2
p
k
，则

(a)a

111


p
1

p
2

< br>p
k



证先证

(p

)p

p

1
。在模p

的完全剩余系1 ,2,,p

中，与p

不互质
的数为p,2p,,p

1
p，共有p

1
个，故

(p

)p

p

1
。

k
< br>k

k
1

1

2

1

1
1

1

2
1
因此，< br>
(a)

(p
1
)

(p
2< br>)

(p
k
)(p
1
p
1
) (p
2
p
2
)(p
k
p
k
)

1

1


1


。< br>
a

111


p
1

p
2


p
k




§4 欧拉定理·费马定理
定理1(Euler)设mZ，m1，(a,m)1，则a

(m)
 1(modm)。
证设r
1
,r
2
,,r

(m )
是模m的简化剩余系，则ar
1
,ar
2
,,ar
< br>(m)
也是模m的简
化剩余系，于是(ar
1
)(ar
2)(ar

(m)
)r
1
r
2
r

(m)
(modm)，
即a

(m)
(r
1< br>r
2
r

(m)
)r
1
r
2< br>r

(m)
(modm)，又(r
1
,m)(r
2
,m)(r

(m)
,m)1，
故(r
1
r
2
r

(m)
,m)1，从而a

(m)< br>1(modm)。
推论(Fermat定理)若p是质数，则a
p
a(mo dp)。
证若(a,p)1，则由定理1可知a
p1
1(modp)，从而a< br>p
a(modp)。

若(a,p)1，则p|a，故a
p
a(modp)。
例1设p是奇质数，证明：
(1)1
p1
2
p1
(p1)
p1
1(modp)；
(2)1
p
2
p
(p1)
p
0(modp)；
mmm(3)若2
m


1(modp)，则12(p1)0(m odp)。
证(1)由费马定理可知i
p1
1(modp)，i1,2,,p 1，
故1
p1
2
p1
(p1)
p1111p11(modp)。
(2)由费马定理可知i
p
i (modp)，i1,2,,p1，
故1
p
2
p
(p 1)
p
12(p1)
p(p1)
0(modp)。2
(3)因为1,2,,p1是模p的简化剩余系，所以2,4,,2(p1)也是模p的 简化
剩余系，于是
1
m
2
m
(p1)
m
2
m
2
m
2
m
2
m
( p1)
m
2
m
[1
m
2
m
( p1)
m
](modp)，
mmm
又2
m

< br>1(modp)，故12(p1)0(modp)。

例2设p是除2 与5外的任一质数，kZ

，证明：p|99

9。

k(p1)个
证因为p2,5，所以(10
k
,p)1，
由费马定理 可知(10
k
)
p1
1(modp)，故
k(p1)个

p|(10
k
)
p1
199

9。< br>