第二节剩余类与完全剩余系第三节缩系教学目的：1、掌握剩余类与完全剩余系的定义与基本性质；2、掌握缩系的定义与基本性质；3、证明及应用Wilson定理；4、证明及应用Fermat小定理、Euler定理的证明及应用；5、掌握Euler函数计算方法及其基本性质.教学重点：1、剩余类与完全剩余系的基本性质；2、证明及应用Wilson定理；3、证明及应用Fermat小定理；4、掌握Eule『函数计算方法及其基本性质.教学课时：8课时教学过程一、剩余类与完全剩余系由上一节我们知道，同余关系满足自反性、对称性、传递性，即对于整数集来说，同余是一个等价关系.这样，可以按同余关系将所有的整数分类.1、定义1给定正整数加，对于每个整数「，0<z<m-l,称集合K?("7)= { ??；n = i (mod m), neZ }是模加的一个剩余类.显然，每个整数必定属于且仅属于某一个(0</<^-1),而且，属于同一剩余类的任何两个整数对模皿是同余的，不同剩余类中的任何两个整数对模”?是不同余的.例如，模5的五个剩余类是K()(5)={…，—10,—5, 0,5, 10,…} &(5)={ ..,-9,-4 J,6 JI,-.- }心5)={ -,-8,-3,2,7,12,--- }心5)={ -,-7,-2,3,8,13,--. }辰(5)={…，_6,—1,4,9,14,…}2、定义2设〃是正整数，从模加的每一个剩余类中任取一个数尢(0 < z < m - 1 称集合｛xo, 口…丸加-1｝是模加的一个完全剩余系(或简称为完全系)・由于占的选取是任意的，所以模加的完全剩余系有无穷多个，通常称(i)｛0,1, 2,…，加一1｝是模m的最小非负完全剩余系;—~ + 1, •••, — 1, 0, 1, •••, — }(当2 I AH)或(ii)乎…—…耳}(当2")是模血的绝对最小完全剩余系.例如,集合｛0,6,7, 13,24｝是模5的一个完全剩余系,集合｛0, 1,2,3,4｝是模5的最小非负完全剩余系.3.定理1整数集合A是模〃的完全剩余系的充要条件是(i) A中含有血个整数;(ii)A中任何两个整数对模血不同余.4、定理2设m> 1, a, Z?是整数，(a, m) = 1, ｛为，恋，…，“加｝是模m的一个完全剩余系，贝!J｛ori + b, 0X2 + b,…,ax m + b｝也是模m的一个完全剩余系.证明：由定理1,只需证明：若XiHXj,贝Ijaxi + b^axj + b (mod m). (1) 事实上，若axi + b = axj + b (mod in),则axi = axj (mod tn),由此得到x： = Xj (mod m),因此Xi = Xj.所以式(1)必定成立.证毕5、定理3 设加1,叱N, AeZ, (A,阳)=1,又设X =｛小/2,…，｝, 丫 = ｛儿」2,…，％2｝，分别是模ni\与模m2的完全剩余系，则/? = ｛ Ax + nuy； xeX, ye Y｝是模ni\ni2的一个完全剩余系.证明：由定理1只需证明：若"，卍UX, y\y H eY,并且Ax' + m\y' =Ax f, + 加］y" (mod 加”血)，(2)事实上，由第一节定理5及式(2),有Ax' =Ax,r (mod m\) =^>=x n (mod m\)=x",再由式(2),又推出m\y' = m\y u (mod mi) =^> y r =y〃(mod /n2) =^>〉，=)'"•推论若加I,"?2W N,(mi, mi) = 1,贝!J当xi与兀2分别通过模加1与模”?2的完全剩余系时，加2兀1 + W1X2通过模加1加2的完全剩余系.6、定理4 设zn/eN (1 </</?),则当药通过模m, (1 <i <n)的完全剩余系时，X = X[ + 72? 1X2 + fUlin2^3+ …+ "7"兀2- 1兀”通过模m\m2 - m n的完全剩余系.证明：对n施行归纳法.当77 = 2时，由定理3知定理结论成立.假设定理结论当n=k时成立，即当七(2KR+1)分别通过模加的完全剩余系时，y = X2 + 加2兀3 + 加2加 1 + …+ my-mkXk +1通过模仍2加3…"《+1的完全剩余系.由定理3,当XI通过模加1的完全剩余系，总(2<i<k+ 1)通过模"•的完全剩余系时，X1 + 777 iy = X1 + 7771(X2 + 加2兀3 + …+ 加 2 …〃以不+ 1)=Xi + H1[X2 + 17772X3 + …+ 叭叱・・皿曲+ 1通过模mim2 - mk+i的完全剩余系.即定理结论对于n = k+\也成立.7、定理5设“wN, A：eZ (1 </<7t),并且满足下面的条件：(i )伽，呦=],1 <ij <n, i 工j；(ii)(A/, ") = 1, 1 <i<n；(iii)m： | Aj , 1 < z,j < n, i rj ・则当七(1 <Z</7)通过模"的完全剩余系&时,y = A[X{ + A 2X2 + …+通过模加"2…的完全剩余系.证明：由定理1只需证明：若1 </</?,则由A\x\ + A2X2' + …+ A n Xn =Aixi n + A2X2,r+ …+ A n Xn r (mod m\ ■ in n) (3) 可以得到xf = x!', \ <i <n.事实上，由条件(iii)及式(3)易得，对于任意的/, 1</</7,有A t Xi =AiXi,r (mod mi).由此并利用条件(ii)和第一节定理5推得x/ = x!' (mod mi),因此xi f=xr.例1设A = {X],X2,…,心}是模加的一个完全剩余系，以{x}表示x 的小数部分，证明：若(a, m) = 1,贝!J£{3}=知1)・i=\ m 2解：当X通过模加的完全剩余系时，俶+ b也通过模加的完全剩余系，因此对于任意的/ (!</•</«), axi + b-定与且只与某个整数j (1 <j</n)同余，即存在整数使得axi 4- Z? = km +j, (1 <j< m)从而評料郭叫用快酣77T m m例2设p>5是素数，…川-2},则在数列a9 2cb 3a, (/? - \ )a, pa中有且仅有一个数b,满足b = 1 (mod p).(5) 此外,若 b = ka,贝I JR HG,ke[2, 3, 2}.解：因为@,p)=l,所以由定理2,式(4)中的数构成模p的一个完全剩余系，因此必有数b满足式(5).设Z? = ka,那么(i ) k 工ci,否则,b = a2 = \ (mod p),即p | (o + 1)(“ - 1),因此# I d - 1 或 # I “ + 1,这与2<a <p -2矛盾；(ii)k 工 \ ,否则，Z? = ltz = 1 (mod /?),这与矛盾；(iii)R H-1,否贝lj, b- -a =\ (mod p),这与矛盾.若又有 L, 2<k r<p-2f使得b = k f a (modp),则k 'a三ka (mod p).因(c/,p)=l,所以k = k1 (mod p),从而p\k- k',这是不可能的.这证明了唯一性.8、定理6 (Wilson定理)设卩是素数，贝I」(p一1)! =-1 (mod p).ffi ：不妨设p>5.由例2容易推出对于2,3,.・显-2,中的每个整 数“，都存在唯一的整数R, 2<k<p-2,使得ka 三 1 (mod /?). (6)因此，整数2,3,…，p_2可以两两配对使得式(6)成立.所以2-3 ..... (p - 2) = 1 (mod p),从而123 ....... (p - 2)(/? - \)=p - 1 = -1 (mod p).例3设m > 0是偶数，｛如,。

2,…，如｝与｛伤，九…，仇,｝都是模m 的完全剩余系,证明：｛⑷+仞心+ /?2,…,4“ + ®”｝不是模加的完全剩 余系.解：因为｛1,2,…，间与仙,如…,心都是模加的完全剩余系,所 以二 吕.m(m +1) m22% - =三〒(mod m). (7) /=i /=1 2 2同理严. m Di = — (mod in).(8)r=l L 如果｛如+ bi, “2 + b 2,…,如+九｝是模m 的完全剩余系,那么也有 艺(©+如三等(mod in).i=i 2联合上式与式(7)和式(8),得到这是不可能的，所以｛如+ bl, U2 +九…,cim +加｝不能是模m 的完 2 2 2 (mod ni),全剩余系.二、缩系在模皿的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们下而对它们做些研究.1、定义1设R是模加的一个剩余类，若有处/?,使得(“,m)=l,则称R是模力的一个简化剩余类.显然，若R是模的简化剩余类，则7?中的每个整数都与用互素.例如，模4的简化剩余类有两个：用(4)={…,-7,-3,1,5,9,— },7?3(4)= { --,-5,-1 ,3,7, 11 , --- }.2、定义2对于正整数k,令函数仅Q的值等于模k的所有简化剩余类的个数，称於)为Eulb函数，或Eu心一°函数.例如，容易验证仅2)=1,讽3) = 2,祕4) = 2,仅7) = 6.显然，仅呦就是在加的一个完全剩余系中与m互素的整数的个数.3、定义3对于正整数m,从模m的每个简化剩余类中各取一个数七，构成一个集合{力,兀2,…,兀酬”)}，称为模加的一个简化剩余系(或简称为简化系或缩系).显然，由于选取方式的任意性，模加的简化剩余系有无穷多个.例如,集合{9, -5, -3,-1}是模8的简化剩余系,集合{1,3, 5,7} 也是模8的简化剩余系，通常称最小非负简化剩余系.4、定理1整数集合A是模加的简化剩余系的充要条件是(i ) A中含有讽》个整数；(ii)A中的任何两个整数对模加不同余；(iii)A中的每个整数都与加互素.5、定理 2 设“是整数，(a, m) = 1, B = [x\,X2, ■ • 是模zn 的简化剩余系,贝！I集合A = {ax\, ax2,心枷)}也是模m的一个缩系.证明:显然,集合A中有讽加个整数.其次，由于(t/,772)=1,所以，对于任意的x,- (1 </ <(p(m)), x,eB,有(与,m)=(七,m)=\.因此,A中的每一个数都与加互素.最后，我们指出，A中的任何两个不同的整数对模加不同余.事实上，若有使得a x f = ax n (mod in),那么，因为(a, m)=所以x r =x r, (mod m),于是x f =x r,.由以上结论及定理1可知集合A是模m的一个缩系.注：在定理2的条件下，若b是整数，集合{ax\ + b, ax^ + /?,,•••, ax^m)+ b}不一定是模加的简化剩余系.例如,取加=4, a= 1, b = l f以及模4 的简化剩余系{1,3}.6、定理3 设m\y 7M2eN, (mi, mi) = L 又设X ={.¥1,X2,---,X<p(…ti)}与丫 = {川，〉'2,…，)‘0 伽2)}分别是模切与加2的缩系，则A = { m\y + mix\ xeX f yeY }是模m\ni2的缩系.证明：若以X，与厂分别表示模加]与牝的完全剩余系，使得Xu X，, Yu厂，贝I」A f = [ ni\y + zmx；xeX f f yeY' }是模“也的完全剩余系.因此只需证明A'中所有与加"2互素的整数的集合R是集合A.显然，若m\y + m/wR，贝'JO^iy + mix,= 1,所以(in\y + mix, m\) = 1,于是("a, ")=1, (x, m\) = 1, xeX.同理可得到ywY,因此/niy + m2xeA.这说明R^A.另一方而，若n?i)? + 则xwX, yeY,即(x,血1)=1, (y\ mi) = 1.由此及伽，加2)= 1得到(mox + m\y, m\) = 加1) = 1以及("?2兀 + 必1” "？2)=(必1幵"？2)= 1 ・因为““与也2互素，所以(血2兀+ 加1加2) = 1，于是+ miyeR・因此A^R.综合以上，得到A = R.7、定理4 设in, /?eN»伽,斤)=1,则(p(mn) =(p(m)(f)(n).证明：这是定理3的直接推论.8、定理5设斤是正整数，门丿2,…，以是它的全部素因数，则(p(n) =〃(1 -—)(1 _ —…(1 _ —!—) = 〃口(1 _ —).Pl Pl Pk P\n P证明：设斤的标准分解式是由定理4得到r=l(p(n)=Y［<p(p^).(1)i=l对任意的素数P，讽严)等于数列1,2,…,〃呻与严(也就是与卩)互素的整数的个数，因此殉产)=p a—［以］十-pg =P a (1-1),p p将上式与式(1)联合，证明了定理.由定理5可知，仅町=1的充要条件是1或2.例1设整数H>2,证明：匸・_1乙l^^n(p(n)9l</<n 2a •刃)=i即在数列1,2,…』中，与”互素的整数之和是卜讽心解：设在1,2, -,77中与n互素的冷)个数是a\. 02,…，a他幷” (CH. 7?) = h \ < Ui < n - \, 1 < / <(p(n), (n - cii, n) = L \<n-ai<n-\y \ <i <(p(n),因此，集合｛di, U2,…，伽”｝与集合也- di, n - U2,…，n - a(p(n)｝是相同的,J •是⑷ + a? + …+ a<p(n)= S _ ⑷)+ (n — ci2)+ …+ (n — a他幷)),2(如+ © +・・・+ a M) = n快",d] +如+…+伽)=切呦.因此例2设〃是正整数，则2>(〃)= n,d\n此处E是对n的所有正约数求和.d\n解：将正整数1,2,…丿按它们与整数”的最大的公约数分类，则n nn =Z1 = Z S 1 = Z Z 1 =工0(了)=工©(〃)・/=1 diJi (tn)=t/ d\n . i n d\n " d\nI —J —1\<i<n d d例3设*N,证明：(i )若"是奇数，则讽4”) = 2仅n)；(ii)刃2)弓”的充要条件是n = 2*,辰N；(iii)刃2)=卜的充要条件是n =刘,k, /eN；(iv)若6 In,则刃2)<»(v )若八-1与斤+1都是素数，n>4,贝^\(p(n) <1/?.解：(i)我们有仅4n)=仅2S) =(p(22)<p(n) = 2 刃J；(ii)若n = 2*,贝lj讽2°"(1冷)=2讥如若(p(n) =-??,设斤= 2®i，2//?i，则由2仅町=讽2切J =讽2。