资源预览内容
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
第9页 / 共11页
第10页 / 共11页
亲,该文档总共11页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第二节 剩余类与完全剩余系第三节 缩系教学目的:1、掌握剩余类与完全剩余系的定义与基本性质;2、掌握缩系的定义与基本性质;3、证明及应用Wilson定理;4、证明及应用Fermat小定理、Euler定理的证明及应用;5、掌握Euler函数计算方法及其基本性质.教学重点:1、剩余类与完全剩余系的基本性质;2、证明及应用Wilson定理;3、证明及应用Fermat小定理;4、掌握Euler函数计算方法及其基本性质.教学过程一、剩余类与完全剩余系由上一节我们知道,同余关系满足自反性、对称性、传递性,即对于整数集来说,同余是一个等价关系. 这样,可以按同余关系将所有的整数分类.1、定义1 给定正整数m,对于每个整数i,0 i m - 1,称集合 Ki(m) = n;n i (mod m),nZ 是模m的一个剩余类.显然,每个整数必定属于且仅属于某一个Ki(m)(0 i m - 1),而且,属于同一剩余类的任何两个整数对模m是同余的,不同剩余类中的任何两个整数对模m是不同余的.例如,模 5的五个剩余类是K0(5) = L , -10, -5, 0 , 5, 10, L ,K1(5) = L , -9 , -4 , 1 , 6 , 11, L ,K2(5) = L , -8 , -3 , 2 , 7 , 12, L ,K3(5) = L , -7 , -2 , 3 , 8 , 13, L ,K4(5) = L , -6 , -1 , 4 , 9 , 14, L .2、定义2 设m是正整数,从模m的每一个剩余类中任取一个数xi(0 i m - 1),称集合x0, x1, L,xm - 1是模m的一个完全剩余系(或简称为完全系).由于xi的选取是任意的,所以模m的完全剩余系有无穷多个,通常称() 0, 1, 2, L, m - 1是模m的最小非负完全剩余系;() 或是模m的绝对最小完全剩余系.例如,集合0, 6, 7, 13, 24是模5的一个完全剩余系,集合0, 1, 2, 3, 4是模5的最小非负完全剩余系.3、定理1 整数集合A是模m的完全剩余系的充要条件是() A中含有m个整数;() A中任何两个整数对模m不同余.4、定理2 设m 1,a,b是整数,(a, m) = 1,x1, x2, L, xm是模m的一个完全剩余系,则ax1 + b, ax2 + b, L, axm + b也是模m的一个完全剩余系.证明:由定理1,只需证明:若xi xj,则axi + baxj + b (mod m). (1)事实上,若 axi + b axj + b (mod m),则 axi axj (mod m),由此得到 xi xj (mod m),因此xi = xj. 所以式(1)必定成立. 证毕 5、定理3 设m1, m2,AZ,(A, m1) = 1,又设,分别是模m1与模m2的完全剩余系,则 R = Ax + m1y;xX,yY 是模m1m2的一个完全剩余系.证明:由定理1只需证明:若x , x X,y , y Y,并且Ax + m1y Ax + m1y (mod m1m2), (2)则 x = x ,y = y .事实上,由第一节定理5及式(2),有 Ax Ax (mod m1) x x (mod m1) x = x ,再由式(2),又推出 m1y m1y (mod m2) y y (mod m2) y = y .推论 若m1, m2N,(m1, m2) = 1,则当x1与x2分别通过模m1与模m2的完全剩余系时,m2x1 + m1x2通过模m1m2的完全剩余系.6、定理4 设mi(1 i n),则当xi通过模mi(1 i n)的完全剩余系时,x = x1 + m1x2 + m1m2x3 + L + m1m2Lmn - 1xn通过模m1m2Lmn的完全剩余系.证明:对n施行归纳法.当n = 2时,由定理3知定理结论成立.假设定理结论当n = k时成立,即当xi(2 i k + 1)分别通过模mi的完全剩余系时,y = x2 + m2x3 + m2m3x4 + L + m2Lmkxk + 1通过模m2m3Lmk + 1的完全剩余系. 由定理3,当x1通过模m1的完全剩余系,xi(2 i k + 1)通过模mi的完全剩余系时,x1 + m1y = x1 + m1(x2 + m2x3 + L + m2Lmkxk + 1)= x1 + m1x2 + m1m2x3 + L + m1m2Lmkxk + 1通过模m1m2Lmk + 1的完全剩余系. 即定理结论对于n = k + 1也成立.7、定理5 设mi,AiZ(1 i n),并且满足下面的条件:() (mi, mj) = 1,1 i, j n,i j;() (Ai, mi) = 1,1 i n;() miAj ,1 i, j n,i j .则当xi(1 i n)通过模mi的完全剩余系Xi时,y = A1x1 + A2x2 + L + Anxn通过模m1m2Lmn的完全剩余系.证明:由定理1只需证明:若xi, xiXi,1 i n,则由A1x1 + A2x2 + L + Anxn A1x1 + A2x2 + L + Anxn (mod m1Lmn) (3)可以得到xi = xi,1 i n.事实上,由条件()及式(3)易得,对于任意的i,1 i n,有 Aixi Aixi (mod mi).由此并利用条件()和第一节定理5推得 xi xi (mod mi),因此xi = xi.例1 设A = x1, x2, L, xm是模m的一个完全剩余系,以x表示x的小数部分,证明:若(a, m) = 1,则. 解:当x通过模m的完全剩余系时,ax + b也通过模m的完全剩余系,因此对于任意的i(1 i m),axi + b一定与且只与某个整数j(1 j m)同余,即存在整数k,使得axi + b = km + j,(1 j m)从而.例2 设p 5是素数,a 2, 3, L, p - 2 ,则在数列 a,2a,3a,L,(p - 1)a,pa (4)中有且仅有一个数b,满足 b 1 (mod p). (5)此外,若b = ka,则k a,k2, 3, L, p - 2.解:因为(a, p) = 1,所以由定理2,式(4)中的数构成模p的一个完全剩余系,因此必有数b满足式(5).设b = ka,那么() k a,否则,b = a2 1 (mod p),即p(a + 1)(a - 1),因此pa - 1或pa + 1,这与2 a p - 2矛盾;() k 1,否则,b = 1a 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 a ka (mod p).因(a, p) = 1,所以k k (mod p),从而pk - k ,这是不可能的. 这证明了唯一性.8、定理6 (Wilson定理) 设p是素数,则(p - 1)! -1 (mod p).证:不妨设p5. 由例2容易推出对于2, 3, L, p - 2,中的每个整数a,都存在唯一的整数k,2 k p - 2,使得 ka 1 (mod p). (6)因此,整数2, 3, L, p - 2可以两两配对使得式(6)成立. 所以23L(p - 2) 1 (mod p),从而 123L(p - 2)(p - 1) p - 1 -1 (mod p).例3 设m 0是偶数,a1, a2, L, am与b1, b2, L, bm都是模m的完全剩余系,证明:a1 + b1, a2 + b2, L, am + bm不是模m的完全剩余系.解:因为1, 2, L, m与a1, a2, L, am都是模m的完全剩余系,所以(mod m). (7)同理 (mod m). (8)如果a1 + b1, a2 + b2, L, am + bm是模m的完全剩余系,那么也有(mod m).联合上式与式(7)和式(8),得到0(mod m),这是不可能的,所以a1 + b1, a2 + b2, L, am + bm不能是模m的完全剩余系.二、缩系在模m的完全剩余系中,与m互素的整数所成的集合有一些特殊的性质,我们下面对它们做些研究.1、定义1 设R是模m的一个剩余类,若有aR,使得(a, m) = 1,则称R是模m的一个简化剩余类.显然,若R是模的简化剩余类,则R中的每个整数都与m互素.例如,模4的简化剩余类有两个:R1(4) = L, -7 , -3, 1 , 5 , 9 , L ,R3(4) = L, -5 , -1 , 3 , 7 , 11 , L .2、定义2 对于正整数k,令函数j(k)的值等于模k的所有简化剩余类的个数,称j(k)为Euler函数,或Eulerj函数.例如,容易验证j(2) = 1,j(3) = 2,j(4) = 2,j(7) = 6.显然,j(m)就是在m的一个完全剩余系中与m互素的整数的个数.3、定义3 对于正整数m,从模m的每个简化剩余类中各取一个数xi,构成一个集合x1, x2, L,xj(m),称为模m的一个简化剩余系(或简称为简化系或缩系).显然,由于选取方式的任意性,模m的简化剩余系有无穷多个.例如,集合9, -5, -3, -1是模8的简化剩余系,集合1, 3, 5, 7也是模8的简化剩余系,通常称最小非负简化剩余系.4、定理1 整数集合A是模m的简化剩余系的充要条件是() A中含有j(m)个整数;() A中的任何两个整数对模m不同余;() A中的每个整数都与m互素.5、定理2 设a是整数,(a, m) = 1,B = x1, x2, L, xj(m)是模m的简化剩余系,则集合A
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号