《初等数论教案第二节剩余类与完全剩余系》由会员分享，可在线阅读，更多相关《初等数论教案第二节剩余类与完全剩余系（30页珍藏版）》请在金锄头文库上搜索。
1、名师归纳总结 精品word资料 - - - - - - - - - - - - - - -其次节剩余类与完全剩余系第三节缩系教学目的： 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 是同余的，不同剩余 第 1 页，共 17 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -类中的任何两个整数对模m 是不同余的 .例如，模5 的五个剩余类是K05 = ,10,5
3、, 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,.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
4、, 1, m1（当 22 | m）是模 m 的肯定最小完全剩余系 .例如，集合0, 6, 7, 13, 24 是模 5 的一个完全剩余系， 集合0, 1, 2,3, 4 是模 5 的最小非负完全剩余系 .3、定理 1整数集合 A 是模 m 的完全剩余系的充要条件是 A 中含有 m 个整数； A 中任何两个整数对模m 不同余 . 第 2 页，共 17 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -4、定理 2设 m1，a，b 是整数， a, m = 1， x1, x2, xm 是模m 的一个完全剩余系，就 ax1b
5、, 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 ,y2 , ym2 ，分别是模 m1 与模 m2 的完全剩余系，就R = Axm1y；xX， yY 是模 m1m2 的一个完全剩余系 .证明： 由定理 1 只需证明：如 x , xX，y , yY，并且Axm
6、1yAxm1ymod m1m2，2就x= x， y= y.事实上，由第一节定理5 及式2，有AxAxmod m1xxmod m1x= x，再由式 2，又推出 第 3 页，共 17 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -m1ym1ymod m2yymod m2y= y.推论如 m1, m2N ， m1, m2 = 1 ，就当 x1 与 x2 分别通过模 m1 与模 m2 的完全剩余系时， m2x1m1x2 通过模 m1m2 的完全剩余系 .6、定理 4设 miN（ 1in），就当 xi 通过模 mi（1in
7、）的完全剩余系时，x = x1m1x2m1m2x3m1m2mn1xn通过模 m1m2mn 的完全剩余系 .证明： 对 n 施行归纳法 .当 n = 2 时，由定理 3 知定理结论成立 .假设定理结论当n = k 时成立，即当 xi（2ik1）分别通过模 mi 的完全剩余系时，y = x2m2x3m2m3x4m2mkxk1通过模 m2m3mk1 的完全剩余系 .由定理 3，当 x1 通过模 m1 的完全剩余系， xi（ 2ik1）通过模 mi 的完全剩余系时，x1m1y = x1m1x2m2x3m2mkxk1= x1m1x2m1m2x3m1m2mkxk1通过模 m1m2mk1 的完全剩余系 .即
8、定理结论对于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 时， 第 4 页，共 17 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -y = A1x1A2x2Anxn通过模 m1m2mn 的完全剩余系 .证明： 由定理 1 只需证明：如 xi , xiXi， 1in，就由A1x1A2x2AnxnA1x1A
9、2x2Anxnmod m1mn 3可以得到 xi= xi， 1in.事实上，由条件 及式 3易得，对于任意的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
10、，（1jm）从而m axibmkj jm j m 1i 1mj 1mj 1mj 1m.m 1 j1mm1m1j 1 mm22例 2设 p5 是素数， a 2, 3, p2 ，就在数列 a， 2a， 3a， p1a，pa4 第 5 页，共 17 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -中有且仅有一个数b，满意b此外，如 b = ka，就 ka， k1 mod p.2, 3, p2.5解： 由于a, p = 1，所以由定理2，式4中的数构成模 p 的一个完全剩余系，因此必有数b 满意式 5.设 b = ka，那
11、么 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 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，从而 第 6 页，共 17 页 - - - - - - - - -名师归纳总结 精品word资料 - - - - - - - - - - - - - - -1 2 3p2p1p11 mod p.例 3 设 m 0 是偶数， a1, a2, , am 与 b1, b2, , bm 都是模 m 的完全剩余系， 证明： a1 b1, a2 b2, , am
