第三节简化剩余系

初等数论第二章同余第三节简化剩余系在模m的完全剩余系中，与m互素的整数所成的集合有一些特殊的性质，我们要在这一节中对它们做些研究。定义1设R是模m的一个剩余类，若有aR，使得(a,m)=1，则称R是模m的一个简化剩余类。显然，若R是模的简化剩余类，则R中的每个整数都与m互素。例如，模4的简化剩余类有两个：R1(4)={,7,3,1,5,9,}，R3(4)={,5,1,3,7,11,}。定义2对于正整数k，令函数(k)的值等于模k的所有简化剩余类的个数，称(k)为Euler函数，或Euler—函数。例如，容易验证(2)=1，(3)=2，(4)=2，(7)=6。显然，(m)就是在m的一个完全剩余系中与m互素的整数的个数。定义3对于正整数m，从模m的每个简化剩余类中各取一个数xi，构成一个集合{x1,x2,,x(m)}，称为模m的一个简化剩余系（或简称为简化系）。显然，由于选取方式的任意性，模m的简化剩余系有无穷多个。例如，集合{9,5,3,1}是模8的简化剩余系，集合{1,3,5,7}也是模8的简化剩余系，通常称最小非负简化剩余系。定理1整数集合A是模m的简化剩余系的充要条件是(ⅰ)A中含有(m)个整数；(ⅱ)A中的任何两个整数对模m不同余；(ⅲ)A中的每个整数都与m互素。证明留作习题。定理2设a是整数，(a,m)=1，B={x1,x2,,x(m)}是模m的简化剩余系，则集合A={ax1,ax2,,ax(m)}也是模m的简化剩余系。证明显然，集合A中有(m)个整数。其次，由于(a,m)=1，所以，对于任意的xi（1i(m)），xiB，有(axi,m)=(xi,m)=1。因此，A中的每一个数都与m互素。最后，我们指出，A中的任何两个不同的整数对模m不同余。事实上，若有x,xB，使得axax(modm)，那么，因为(a,m)=1，所以xx(modm)，于是x=x。由以上结论及定理1可知集合A是模m的一个简化系。证毕。注：在定理2的条件下，若b是整数，集合{ax1b,ax2b,,,ax(m)b}不一定是模m的简化剩余系。例如，取m=4，a=1，b=1，以及模4的简化剩余系{1,3}。定理3设m1,m2N，(m1,m2)=1，又设},,,{},,,{)(21)(2121mmyyyYxxxX与分别是模m1与m2的简化剩余系，则A={m1ym2x；xX，yY}是模m1m2的简化剩余系。证明由第二节定理3推论可知，若以X与Y分别表示模m1与m2的完全剩余系，使得XX，YY，则A={m1ym2x；xX，yY}是模m1m2的完全剩余系。因此只需证明A中所有与m1m2互素的整数的集合R是集合A。显然，AA’。若m1ym2xR，则(m1ym2x,m1m2)=1，所以(m1ym2x,m1)=1，于是(m2x,m1)=1，(x,m1)=1，xX。同理可得到yY，因此m1ym2xA。这说明RA。另一方面，若m1ym2xA，则xX，yY，即(x,m1)=1，(y,m2)=1。由此及(m1,m2)=1得到(m2xm1y,m1)=(m2x,m1)=1以及(m2xm1y,m2)=(m1y,m2)=1。因为m1与m2互素，所以(m2xm1y,m1m2)=1，于是m2xm1yR。因此AR。综合以上，得到A=R。证毕。定理4设m,nN，(m,n)=1，则(mn)=(m)(n)。证明这是定理3的直接推论。证毕。定理5设n是正整数，p1,p2,,pk是它的全部素因数，则(n)=npkpnpppn|21)()())((11111111。证明设n的标准分解式是n=kiiip1，由定理4得到(n)=kiiip1)(。(1)对任意的素数p，(p)等于数列1,2,,p中与p（也就是与p）互素的整数的个数，因此(p)=p)(][111pppppp，将上式与式(1)联合，证明了定理。证毕。由定理5可知，(n)=1的充要条件是n=1或2。例1设整数n2，证明：1),(121niniin(n)，即在数列1,2,,n中，与n互素的整数之和是21n(n)。解设在1,2,,n中与n互素的(n)个数是a1,a2,,a(n)，(ai,n)=1，1ain1，1i(n)，则(nai,n)=1，1nain1，1i(n)，因此，集合{a1,a2,,a(n)}与集合{na1,na2,,na(n)}是相同的，于是a1a2a(n)=(na1)(na2)(na(n))，2(a1a2a(n))=n(n)，因此a1a2a(n)=21n(n)。例2设n是正整数，则ndd|)(=n，此处nd|是对n的所有正约数求和。解将正整数1,2,,n按它们与整数n的最大的公约数分类，则n=nindnidninddndidndindndddn1|1),(|11),(||)()(111。例3设nN，证明：(ⅰ)若n是奇数，则(4n)=2(n)；(ⅱ)(n)=n21的充要条件是n=2k，kN；(ⅲ)(n)=n31的充要条件是n=2k3l，k,lN；(ⅳ)若6n，则(n)n31；(ⅴ)若n1与n1都是素数，n4，则(n)n31。解(ⅰ)我们有(4n)=(22n)=(22)(n)=2(n)；(ⅱ)若n=2k，则(2k)=nkk21221121)(，若(n)=n21，设n=2kn1，2|n1，则由n21=(n)=(2kn1)=(2k)(n1)=2k1(n1)=11111)(21)(221nnnnnnk推出(n1)=n1，所以n1=1，即n=2k；(ⅲ)若n=2k3l，则(n)=(2k)(3l)=nlk3131132112)()(。若(n)=n31，设n=2k3ln1，6|n1，则由1111)(31)()3()2()32()(31nnnnnnnlklk推出(n1)=n1，所以n1=1，即n=2k3l；(ⅳ)设n=2k3ln1，6|n1，则(n)=(2k)(3l)(n1)=nnnlklk313231)(323111；(ⅴ)因为n4，所以n1与n1都是奇素数，所以n是偶数。因为n13，所以n1与n1都不等于3，当然不被3整除，所以3n，因此6n。再由上面已经证明的结论(ⅳ)，即可得到结论(ⅴ)。例4证明：若m,nN，则(mn)=(m,n)([m,n])；解显然mn与[m,n]有相同的素因数，设它们是pi（1ik），则。，)())(()())((111111],[]),([111111)(2121kkpppnmnmpppmnmn由此两式及mn=(m,n)[m,n]即可得证。习题三1.证明定理1。2.设m1,m2,,mn是两两互素的正整数，xi分别通过模mi的简化剩余系（1in），m=m1m2mn，Mi=imm，则M1x1M2x2Mnxn通过模m的简化剩余系。3.设m1，(a,m)=1，x1,x2,,x(m)是模m的简化剩余系，证明：)(1)(21}{miimmax。其中{x}表示x的小数部分。4.设m与n是正整数，证明：(mn)((m,n))=(m,n)(m)(n)。5.设a，b是任意给定的正整数，证明：存在无穷多对正整数m与n，使得a(m)=b(n)。6.设n是正整数，证明：(ⅰ)(n)n21；(ⅱ)若n是合数，则(n)nn。