初等数论第三章同余

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

2、关系。定理1 整数 a, b 对模 m 同余的充分必要条件是m | (a b)，即a b mt，t Z。证明设a mq1 r1， bmq2r2， 0 r1 , r2m，则 ab (modm)r1 r2 a bm(q1 q2 )m | (ab)。性质1 (1) 若 a1b1(modm)，a2b2 (mod m)，则 a1a2b1b2(mod m)；(2) 若ab c (mod m)，则a cb (mod m)。性质2 若 a1 b1 (modm)，a2b2(modm)，则a1a2b1b2(modm)；特别地，若a b (mod m)，则ka kb (mod m)。定理2 若 A 1 k B 1

3、k (mod m)， xi yi (mod m)， i 1,2, k，则 A 1 k x1 1 xk1kB 1 k y1 1ykk (mod m)；特别地，若ai bi (mod m)，1knn1a0bnx bn 1xb0 (mod m)。nn1i 0,1,2, n，则anxan 1x性质3 若 a a1d， b b1d， (d , m) 1， a b (mod m)，则a1 b1 (mod m)。性质4 (1) 若 a b (mod m)， k 0，则ak bk (mod mk)；(2) 若 a b (mod m)， d是 a, b及 m的任一公因数，则a b (mod m )。dd d性质

4、5 若 a b (mod mi )， i 1,2, , k，则a b (mod m1 , m2 , , mk )。反之亦然。性质6 若 a b (mod m)， d | m， d 0，则a b (mod d )。性质7 若 a b (mod m)，则(a, m) (b, m)，因而若d能整除a,b及 m两数之一，则d必能整除a, b中的另一数。例1 求 3406 写成十进位数时的个位数码。解 事实上，只需求满足3406 a (mod 10)， 0 a 9的数a。因为32 91 (mod 10)，所以3406 (32 )203 ( 1) 2031 9 (mod 10)，即个位数码是9。例2 证明

5、：当n为奇数时，3 | 2n 1，当n为偶数时，3 | 2n 1。证明 因为 21 (mod 3)， 所以 2n 1 ( 1)n 1 (mod 3)，当 n为奇数时，2n 1 ( 1)n 11 1 0 (mod 3)，故3|2n 1，当 n为偶数时，2n 1 ( 1)n 1 1 1 2 (mod 3)，故3 | 2n1。同余性质在算术中的一些应用。一、检查因数的方法1、一整数能被3(或9)整除的充分必要条件是它的十进位数码之和能被3(或9)整除。证明 只需讨论正整数即可。任取a Z ，则 a 可以写成十进位的形式：a an10n an 110n 1a0， 0 ai 10，于是，由10 1 (m

6、od 3)可知a a n an 1a0 (mod 3)，从而3 | a 3 | a n a n 1a0。对于9 同理可证。2、设正整数aan1000nan11000n1a0，0ai1000，则7(或11 或13)| a的充分必要条件是7(或11 或 13) |(a0a2)(a1a3)。证明 因为 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

7、， P=ab=15，检查计算是否正确。解 令 a an10n an 110n 1a0， 0 ai 10b bm10m bm 110m 1b0， 0 bj 10ll1P cl 10cl 1 10c0， 0 ck 10则(ai)(bj) ck (mod 9)( *)i0j0k0若( *)不成立，则P ab，故在本题中，计算不正确。注 (1) 若( *)不成立，则计算不正确；但否命题不成立。(2) 利用同样的方法可以用来验证整数的加、减运算的正确性。2 剩余类及完全剩余系定理1 设 m 0，则全体整数可分成m个集合，记作：K0,K1, , Km 1，其中 Kr qm r |q Z， r 0,1, ,

8、m 1，这些集合具有下列性质：(1)每个整数必包含在而且仅在上述的一个集合中；(2) 两个整数同在一个集合的充分必要条件是对模m同余。证 (1) 设 a是任一整数，则必有a mq ra， 0 ra m，于是由 r 的存在性可知a K ，由 r 的唯一性可知a只能在K 中。araara(2) 设整数 a, b K r，则 a mq1 r ， b mq2r，故a b (mod m)。反之，若a b (mod m)，则a, b必处于同一K r中。定义1 定理1中的K0,K1, , Km 1称为模m的剩余类，一个剩余类中的任一数称为它同类数的剩余。若 m个整数a0,a1, ,am1中任何两个数都不在同

9、一剩余类，则a0,a1, ,am 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)am a,( 1)m 1m (m 1)；(4)当 m为偶数时，1mm1, 221,0,1,1；mmm1, , 1,0,1, ,1, ；m为奇数时，m122221,0,1, , m 1。(绝对最小完全剩余系)2定理2 设 m Z ， (a, m) 1， b Z，若x通过模m的一个完全剩余系，则ax

10、 b也通过模m的一个完全剩余系，即若 a0 ,a1, ,am 1是模m的完全剩余系，则 aa0 b, aa1 b, , aam 1 b也是模m的完全剩余系。证只需证明aa0 b,aa1 b, aam 1b两两不同余即可，采用反证法。设 aaibaa j b (mod m) (i j )，则 aai aa j (mod m)，又 (a, m) 1，于是ai aj (mod m) (ij)，与已知矛盾，故 aa0b, aa1 b, , aam 1 b也是模m的完全剩余系。定理3 设 m1, m2 Z ， (m1,m2) 1，而x1 ,x2 分别通过模m1,m2的完全剩余系，则m2x1 m1x2也通

11、过模m1m2的完全剩余系。证 因为x1,x2 分别通过m1,m2 个整数，所以m2x1 m1x2通过m1m2 个整数，下证这 m1m2 个整数对模m1 m2两两不同余。设 m2x1 ' m1x2' m2 x1 '' m1x2' '(mod m1m2 )，其中x1' , x1 '' , x2' , x2 ''分别是x1 , x2 所通过的完全剩余系中的数，则m2x1' m2x1'' (mod m1 )， m1x2 ' m1x2'' (mod m2 )，又

12、(m1 ,m2)1，故x1'x1 '' (mod m1 )，x2 'x2'' (modm2)，这说明m2x1m1 x2所通过的数两两不同余，因此，m2x1m1x2也通过模m1m2的完全剩余系。例1 设 m 0 (mod2)， a1, ,am及 b1, ,bm都是模m的完全剩余系，则a1b1 , , am bm不是模m的完全剩余系。证 ：因为 a1 , a m 及 b1 , bm都是模m的完全剩余系，m所以i1aimii1m( m 1)m(mod m)，同理bi2i1m2 (mod m)，m从而i1(aibi)maii1i1mmbi0 (mod m

13、)，22若 a1b1,ama1b1 ,mbm是模m的完全剩余系，则(aii1, a m bm 不是模m的完全剩余系。mbi )(mod m)，矛盾。例2证明：对任何正整数证：考察 n1个数： 1,11,n ，存在着仅有数字1,0组成的数a，使得n | a。,111，它们对模n至少有两个在同一同余类中，1个 1设 b c，b 11k个 11， c 11 1，s个 1c (mod n)，则n | (b c) 11 1 00 0k s个 1 s个 0a。例3设 m Z ， (a,m) 1， bZ， x通过模m的一个完全剩余系，ax b 1则( m 1)。xm 2证 因为 x通过模m的一个完全剩余系，

14、所以 ax b通过模m的一个完全ax b 0 1 m 1剩余系， 从而通过 , ,，m mm max bm01mmm1m1(m 1)。2§ 3 简化剩余系与欧拉函数定义1 欧拉函数(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互质的剩

15、余类的个数为(m)，模m的每一简化剩余系是由与 m互质的(m)个对模m不同余的整数组成的。证 设 K0,K1, ,Km 1是模m的全部剩余类，若Kr与模m互质，则(r,m) 1；反之，若有krKr，(kr ,m)1，则对于Kr中任一数kr 'qmkr，有(kr ',m)1，即 Kr与模m互质。定理2 若 a1,a2, ,a (m)是(m)个与m互质的整数，并且两两对模m不同余，则 a1,a2, ,a (m)是模m的一个简化剩余系。定理3 若 (a, m) 1， x通过模 m的简化剩余系，则ax也通过模m的简化剩余系。证ax通过(m)个整数，而且由(a, m) 1， (x,m)

16、1可知(ax,m) 1，若 axi axj (mod m) (ij )，则xi xj (mod m) (ij)，与已知矛盾，故 ax 通过模m的简化剩余系。定理4 设 m1,m2 Z ， (m1,m2) 1，而x1,x2 分别通过模m1,m2的简化剩余系，则m2x1 m1 x2也通过模m1m2的简化剩余系。证 由上一节定理3可知，若x1 ,x2 分别通过模m1 , m2的完全剩余系，则m2x1 m1x2 也通过模m1 m2的完全剩余系。下证当x1,x2 分别通过模 m1,m2的简化剩余系时，m2x1 m1x2通过模m1m2的一个完全剩余系中一切与m1m2 互质的整数。一方面，由(x1 , m1

17、 )(x2 , m2 )(m1, m2 )1可知(m2x1 , m1)1，(m1 x2 , m2 )1，于是(m2x1m1 x2, m1)1，(m1 x2m2x1 , m2)1，从而(m2 x1m1 x2 , m1 m2 )1，另一方面，由(m2x1m1x2 , m1m2 )1可知(m2x1m1 x2 , m1)(m1 x2m2x1 , m2 )1，于是(m2x1 , m1 ) (m1x2 , m2 ) 1，从而(x1 , m1 ) (x2 , m2 ) 1。推论 设 m1 , m2 Z ， (m1 , m2) 1，则(m1m2)(m1) (m2)。证 由定理4可知，若x1 ,x2分别通过模m

18、1 , m2的简化剩余系，则m2x1 m1x2通过模m1m2的简化剩余系，即m2x1 m1x2通过(m1 m2 )个整数。另一方面，由于x1通过(m1)个整数，x2通过( m2)个整数，因此，m2x1 m1x2通过 (m1 ) (m2)个整数。故(m1 m2)(m1 ) (m2)。111定理5 设 a p1 1 p22pk k，则(a) a 111。p1p2pk证 先证 ( p ) p p 1。在模p 的完全剩余系1,2, , p 中，与 p 不互质的数为 p,2 p, , p 1 p，共有p 1个，故 (p ) p p 1。因此，(a)(p1 1 )( p22)(pkk)(p11 p11 1

19、)(p21p221)(pkkpkk 1)a11pk111p1p24 欧拉定理·费马定理定理1 (Euler) 设 m Z， m 1， (a, m) 1，则a (m) 1 (mod m)。证 设r1,r2,r (m)是模m的简化剩余系，则ar1,ar2, ,ar (m)也是模m的简化剩余系，于是(ar1)(ar2 )(ar (m) ) r1 r2r (m) (mod m)，即 a (m)(r1r2r (m) )r1 r2r (m) (mod m)，又 (r1 ,m)(r2,m) (r (m) , m) 1，故(r1r2 r (m),m) 1，从而a (m) 1 (modm)。推论(Fermat定理) 若 p是质数，则a p a