初等数论教案第二节剩余类与完全剩余系

1、其次节剩余类与完全剩余系第三节缩系教学目的： 1、把握剩余类与完全剩余系的定义与基本性质； 2、把握缩系的定义与基本性质； 3、证明及应用wilson 定理；4、证明及应用 fermat 小定理、 euler 定理的证明及应用；5、把握 euler 函数运算方法及其基本性质.教学重点： 1、剩余类与完全剩余系的基本性质； 2、证明及应用wilson 定理； 3、证明及应用 fermat 小定理；4、把握 euler 函数运算方法及其基本性质.教学课时： 8 课时教学过程一、剩余类与完全剩余系由上一节我们知道，同余关系满意自反性、对称性、传递性，即 对于整数集来说，同余是一个等价关系.这样，可以

2、按同余关系将全部的整数分类 .1、定义 1给定正整数 m，对于每个整数i， 0im1，称集合kim = n；ni mod m，nz 是模 m 的一个剩余类 .明显，每个整数必定属于且仅属于某一个kim（0im1），而且，属于同一剩余类的任何两个整数对模m 是同余的，不同剩余类中的任何两个整数对模m 是不同余的 .例如，模5 的五个剩余类是k05 = ,10,5, 0 , 5, 10, ，k15 = ,9 ,4 , 1 , 6 , 11, ，k25 = ,8 ,3 , 2 , 7 , 12, ，k35 = ,7 ,2 , 3 , 8 , 13, ，k45 = ,6 ,1 , 4 , 9 , 14

3、,.2、定义 2设 m 是正整数，从模m 的每一个剩余类中任取一个数 xi（ 0im1），称集合 x0, x1,xm1 是模 m 的一个完全剩余系（或简称为完全系）.由于 xi 的选取是任意的，所以模m 的完全剩余系有无穷多个，通常称m或 0, 1, 2, m1 是模 m 的最小非负完全剩余系； m1,2,1,0, 1, m （当22 |）m1 , 2,1,0, 1, m1（当 22 | m）是模 m 的肯定最小完全剩余系 .例如，集合0, 6, 7, 13, 24 是模 5 的一个完全剩余系， 集合0, 1, 2,3, 4 是模 5 的最小非负完全剩余系 .3、定理 1整数集合 a 是模 m

4、 的完全剩余系的充要条件是 a 中含有 m 个整数； a 中任何两个整数对模m 不同余 .4、定理 2设 m1，a，b 是整数， a, m = 1， x1, x2, xm 是模m 的一个完全剩余系，就 ax1b, ax2b, axmb 也是模 m 的一个完全剩余系 .证明： 由定理 1，只需证明：如xixj ，就axibaxjb mod m.1事实上，如axibaxjb mod m，就axiaxj mod m，由此得到xixj mod m，因此 xi = xj.所以式 1必定成立 .证毕5、定理 3设 m1, m2n，az， a, m1 = 1，又设x x1 , x2 , xm1 ， y y1

5、 ,y2 , ym2 ，分别是模 m1 与模 m2 的完全剩余系，就r = axm1y；xx， yy 是模 m1m2 的一个完全剩余系 .证明： 由定理 1 只需证明：如 x , xx，y , yy，并且axm1yaxm1ymod m1m2，2就x= x， y= y.事实上，由第一节定理5 及式2，有axaxmod m1xxmod m1x= x，再由式 2，又推出m1ym1ymod m2yymod m2y= y.推论如 m1, m2n ， m1, m2 = 1 ，就当 x1 与 x2 分别通过模 m1 与模 m2 的完全剩余系时， m2x1m1x2 通过模 m1m2 的完全剩余系 .6、定理

6、4设 min（ 1in），就当 xi 通过模 mi（1in）的完全剩余系时，x = x1m1x2m1m2x3m1m2mn1xn通过模 m1m2mn 的完全剩余系 .证明： 对 n 施行归纳法 .当 n = 2 时，由定理 3 知定理结论成立 .假设定理结论当n = k 时成立，即当 xi（2ik1）分别通过模 mi 的完全剩余系时，y = x2m2x3m2m3x4m2mkxk1通过模 m2m3mk1 的完全剩余系 .由定理 3，当 x1 通过模 m1 的完全剩余系， xi（ 2ik1）通过模 mi 的完全剩余系时，x1m1y = x1m1x2m2x3m2mkxk1= x1m1x2m1m2x3m

7、1m2mkxk1通过模 m1m2mk1 的完全剩余系 .即定理结论对于n = k1 也成立 .7、定理 5设 min， aiz （ 1in），并且满意下面的条件： mi, mj = 1，1i, jn，ij ； ai, mi = 1， 1in； miaj，1i, jn，ij .就当 xi （1in）通过模 mi 的完全剩余系xi 时，y = a1x1a2x2anxn通过模 m1m2mn 的完全剩余系 .证明： 由定理 1 只需证明：如 xi , xixi， 1in，就由a1x1a2x2anxna1x1a2x2anxnmod m1mn 3可以得到 xi= xi， 1in.事实上，由条件 及式 3易

8、得，对于任意的i ，1in，有 ai xiai ximod mi .由此并利用条件 和第一节定理 5 推得xiximod mi，因此 xi= xi.例 1设 a = x1, x2, xm 是模 m 的一个完全剩余系，以 x 表示x 的小数部分，证明：如a, m = 1，就m axibi 1m1 m21 .解： 当 x 通过模 m 的完全剩余系时， axb 也通过模 m 的完全剩余系，因此对于任意的i（ 1im）， axib 肯定与且只与某个整数 j（1jm）同余，即存在整数k，使得axib = kmj，（1jm）从而m axibmkj jm j m 1i 1mj 1mj 1mj 1m.m 1

9、j1mm1m1j 1 mm22例 2设 p5 是素数， a 2, 3, p2 ，就在数列 a， 2a， 3a， p1a，pa4中有且仅有一个数b，满意b此外，如 b = ka，就 ka， k1 mod p.2, 3, p2.5解： 由于a, p = 1，所以由定理2，式4中的数构成模 p 的一个完全剩余系，因此必有数b 满意式 5.设 b = ka，那么 ka，否就， b = a21 mod p，即 pa1a1，因此 pa1 或 pa1，这与 2ap2 冲突； k 1，否就， b = 1 a 1 mod p，这与 2 a p 2 冲突； k 1，否就， b = a 1 mod p，这与 2 a

10、 p 2 冲突. 如又有 k ，2 k p 2，使得 b k a mod p，就k aka mod p.因a, p = 1 ，所以 kkmod p，从而 pkk ，这是不行能的 .这证明白唯独性 .8、定理 6 wilson 定理设 p 是素数，就p1.1 mod p.证：不妨设 p5.由例 2 简洁推出对于 2, 3, p2，中的每个整数 a，都存在唯独的整数k，2kp2，使得ka1 mod p.6因此，整数 2, 3, p2 可以两两配对使得式 6成立.所以2 3p21 mod p，从而1 2 3p2p1p11 mod p.例 3 设 m > 0 是偶数， a1, a2, , am

11、与 b1, b2, , bm 都是模 m 的完全剩余系， 证明： a1 b1, a2 b2, , am bm 不是模 m 的完全剩余系.解：由于1, 2, m 与 a1, a2, am 都是模 m 的完全剩余系， 所以mmaiii 1i1mm12m2 mod m.7同理mm2bimod m.8i 1假如 a1b1, a2b2, ambm 是模 m 的完全剩余系，那么也有mmaibi mod m.i 12联合上式与式 7和式8，得到0mm22m mod m，2这是不行能的， 所以 a1b1, a2b2, ambm 不能是模 m 的完全剩余系 .二、缩系在模 m 的完全剩余系中， 与 m 互素的整

12、数所成的集合有一些特别的性质，我们下面对它们做些讨论.1、定义 1设 r 是模 m 的一个剩余类， 如有 ar，使得a, m = 1，就称 r 是模 m 的一个简化剩余类 .明显，如 r 是模的简化剩余类，就r 中的每个整数都与m 互素.例如，模 4 的简化剩余类有两个：r14 = ,7 ,3, 1 , 5 , 9 , ，r34 = ,5 ,1 , 3 , 7 , 11 ,.2、定义 2对于正整数 k，令函数k的值等于模 k 的全部简化剩余类的个数，称k为 euler 函数，或 euler函数.例如，简洁验证2 = 1， 3 = 2， 4 = 2， 7 = 6.明显， m就是在 m 的一个完全

13、剩余系中与m 互素的整数的个数 .3、定义 3对于正整数 m，从模 m 的每个简化剩余类中各取一个数 xi，构成一个集合 x1, x2,x m ，称为模 m 的一个简化剩余系 （或简称为简化系或缩系）.明显，由于选取方式的任意性，模m 的简化剩余系有无穷多个.例如，集合 9,5,3,1 是模 8 的简化剩余系，集合 1, 3, 5, 7也是模 8 的简化剩余系，通常称最小非负简化剩余系.4、定理 1整数集合 a 是模 m 的简化剩余系的充要条件是 a 中含有m个整数； a 中的任何两个整数对模m 不同余； a 中的每个整数都与m 互素.5、定理 2设 a 是整数， a, m = 1 ， b =

14、 x1, x2, x m 是模 m的简化剩余系，就集合a = ax1, ax2, ax m 也是模 m 的一个缩系 .证明 ：明显，集合 a 中有 m个整数 .其次，由于 a, m = 1，所以，对于任意的 x（i1im），xib，有axi, m = xi, m = 1.因此，a 中的每一个数都与m 互素.最终，我们指出， a 中的任何两个不同的整数对模 m 不同余 .事实上，如有 x , xb，使得a xaxmod m，那么，由于 a, m = 1，所以 xxmod m，于是 x= x.由以上结论及定理 1 可知集合 a 是模 m 的一个缩系 .注：在定理 2 的条件下，如 b 是整数，集合

15、 ax1b, ax2b, ax mb不肯定是模 m 的简化剩余系 .例如，取 m = 4，a = 1，b = 1，以及模 4的简化剩余系 1, 3.6、定理 3设 m1, m2n，m1, m2 = 1，又设x x1 , x2 , x m1 与 y y1 , y2 , y m2 分别是模 m1 与 m2 的缩系，就a = m1ym2x； xx， yy 是模 m1m2 的缩系 .证明： 如以 x 与 y 分别表示模 m1 与 m2 的完全剩余系，使得x x ，yy ，就a= m1ym2x；xx ，yy是模 m1m2 的完全剩余系 .因此只需证明 a 中全部与 m1m2 互素的整数的集合 r 是集合

16、 a.明显， aa.如 m1ym2xr，就m1ym2x, m1m2 = 1，所以m1ym2x, m1 = 1，于是m2x, m1 = 1，x, m1 = 1，xx.同理可得到 yy，因此 m1ym2xa.这说明 ra.另一方面，如 m1ym2xa，就 xx， yy，即x, m1 = 1， y, m2 = 1.由此及 m1, m2 = 1 得到m2xm1y, m1 = m2x, m1 = 1以及m2xm1y, m2 = m1y, m2 = 1.由于 m1 与 m2 互素，所以m2xm1y, m1m2 = 1，于是 m2xm1yr.因此 ar.综合以上，得到a = r.7、定理 4设 m, nn，

17、 m, n = 1，就mn =mn.证明： 这是定理 3 的直接推论 .8、定理 5设 n 是正整数， p1, p2, pk 是它的全部素因数，就n = n11 11 p1p211 pkn1p| n1 .pk证明： 设 n 的标准分解式是n =i 1p ii，由定理 4 得到kn = p i i .1i 1对任意的素数 p， p 等于数列 1, 2, p 中与 p （也就是与 p）互素的整数的个数，因此p = p pp pp1p11 ，p将上式与式 1联合，证明白定理 .由定理 5 可知，n = 1 的充要条件是 n = 1 或 2.例 1设整数 n2，证明：i1nn，1 i n2i , n

18、1即在数列 1, 2, n 中，与 n 互素的整数之和是解： 设在 1, 2, n 中与 n 互素的n个数是1 nn.2a1, a2, a n，ai, n = 1， 1ain1，1in， 就nai, n = 1，1nain1，1in，因此，集合 a1, a2, a n 与集合 na1, na2, na n 是相同的，于是a1a2a n = na1na2na n，2a1a2a n = nn，因此a1a2a n = 1 n n.2例 2设 n 是正整数，就d |n d = n，此处d|n是对 n 的全部正约数求和 .解：将正整数 1, 2, n 按它们与整数n 的最大的公约数分类， 就nn =1i

19、 11d|n i , n d1d |n i , n 1d|n n dd |nd .1 i nd d1 indd例 3设 nn，证明： 如 n 是奇数，就4n = 2n； n = 1 n 的充要条件是 n = 2k，kn；2 n = 1 n 的充要条件是n = 2k3l ，k, ln；3 如 6n，就n1 n ；3 如 n1 与 n1 都是素数， n > 4，就n解： 我们有4n =22n =22n = 2n；1 n .3 如 n = 2k，就2k = 2 k 11 22 k 11 n ，2如 n = 1 n ，设 n = 2kn1， 2 | n1，就由21 n =n =2kn1 =2kn

20、1 =2k1n12= 1 2 k n12 n1 n11 nn12 n1推出n1 = n1，所以 n1 = 1，即 n = 2k； 如 n = 2k3l，就n =2k3l = 2 k 1如 n = 1 n ，设 n = 2k3l n1， 6 | n1，就由31 3l 11231 n .31 nn32 k 3 ln1 2 k 3l n1 1n1 n3n1推出n1 = n1，所以 n1 = 1，即 n = 2k3l； 设 n = 2k3ln1，6 | n1，就n =2k3l n1 = 1 2k 3l3n1 1 2k 3l n 31 n ；13 由于 n > 4，所以 n1 与 n1 都是奇素数

21、，所以n 是偶数 .由于 n1 > 3，所以 n1 与 n1 都不等于 3，当然不被 3 整除，所以 3n，因此 6n.再由上面已经证明的结论，即可得到结论 .例 4证明：如 m, nn，就mn = m, n m, n；解： 明显 mn 与m, n 有相同的素因数，设它们是pi（ 1ik），就mnmn11 1p11 1p21 ，p k m, n m, n11 1p11 1p 21 ；pk由此两式及 mn = m, n m, n即可得证 .三、euler 定理与 fermat 小定理1、定理 1 euler设 m 是正整数， a, m = 1，就am1 mod m.证明： 由第三节定理 2

22、，设 x1, x2, x m 是模 m 的一个简化剩余系，就 ax1, ax2, ax m 也是模 m 的简化剩余系，因此ax1ax2ax mx1x2,x m mod m，a mx1x2x mx1x2,x m mod m.1由于x1x2x m, m = 1，所以由式 1得出a m1 mod m.2、定理 2fermat设 p 是素数，就对于任意的整数a，有a pa mod p.证明： 如a, p1，就由定理 1 得到a p11 mod pa pa mod p.如a, p > 1，就 pa，所以a p0a mod p.例 1设 n 是正整数，就 5 | 1n2n3n4n 的充要条件是 4n

23、.解由于5 = 4，所以，由定理2k41 mod 5，1k4.因此，如 n = 4qr ，0r3，就1n2n3n4n1r2r3r4r1r2r2r1r mod 5， 2用 r = 0， 1， 2，3， 4 分别代入式 2即可得出所需结论 .例 2设 x1, x2, x m 是模 m 的简化剩余系，就x1x2x m21 mod m.解记 p = x1x2x m，就p, m = 1.又记yi =p ，1im，xi就 y1, y2, y m 也是模 m 的简化剩余系，因此mx im pmod m，i 1i1 xi再由 euler 定理，推出p2p m1 mod m.例 3设a, m = 1， d0 是

24、使a d1 mod m成立的最小正整数，就 d0m； 对于任意的 i， j，0i, jd01，ij ，有a ia j mod m.3解： 由 euler 定理， d0m，因此，由带余数除法，有m = qd0r ，qz ， q > 0， 0r < d0.因此，由上式及d0 的定义，利用定理1，我们得到1a ma qd0 ra r mod m，即整数 r 满意a r1 mod m ，0r < d0 .由 d0 的定义可知必是r = 0，即 d0m； 如式3不成立，就存在i， j， 0i, jd01，ij ，使得a ia j mod m.不妨设 i > j .由于a, m =

25、 1，所以aij0 mod m， 0 < ij < d0.这与 d0 的定义冲突，所以式 3必成立 .例 4设 a，b，c， m 是正整数， m > 1， b, m = 1，并且b a1 mod m， b c1 mod m，4记 d = a, c，就 bd1 mod m.解： 利用辗转相除法可以求出整数x，y，使得 axcy = d，明显 xy < 0.如 x > 0，y < 0，由式 4知1b ax = b dbcy = b db cyb d mod m.如 x < 0，y > 0，由式 4知1b cy = b dbax = b dbaxb d

26、 mod m.例 5设 p 是素数， pbn1， nn，就下面的两个结论中至少有一个成立： pbd1 对于 n 的某个因数 d < n 成立； p1 mod n .如 2 | n，p > 2，就 中的 mod n 可以改为 mod 2n.解： 记 d = n, p1，由 b n1，b p11 mod p，及例题 4，有b d1 mod p.如 d < n，就结论 得证.如 d = n，就 np1，即 p1 mod n，这就是结论 .如 2 | n，p > 2，就 p1 mod 2.由此及结论 ，并利用同余的基本性质，得到 p1 mod 2n.注：例 5 供应了一个求素因数的方法，就是说，整数 bn 1 的素因数 p，是 bd 1（当 d n 时）的素因数， 或者是形如 kn 1 的数（当2 | n，p > 2 时，是形如 2kn 1 的数.例 6将 2111 = 20