第二章一次不定方程(4)(消去律）若(ai,m)=1,且aic三bid (modm)，则c=d(modm)(5）（乘法逆元）若(a1.m)=1，则存在aEZ，使得aia=1(modm)，并且a在模m的同余下是唯一的，常记作a=l(modm)证明(1)是显然的(2)我们有aa2 - bib2 = a2(a1 -b1) + bi(a2 - b2)因m[a1 -bi,m|a2-b2,故得m[aia2-bib2,即aia2=bib2 (mod m)。(3)设a1=mq+r是带余数除法,则1=(a1,m)=(r,m).因bi被m除的余数也是r,所以类似也可得(b,m）=(r,m）=1.(4) aic-bid=ai(c-d)+(a1-bi)d.因为m |aic-bid, m| ai-bi,所以m|ai(c-d)又因为（ai.m）=1,故由消去律得mc-d,即c=d(modm)(5)由推论2.2.1,存在a,yeZ,使得a1a+my=(a1,m)=1,即m(-y)=a1a-1.这就推■出mai-1,即air=1(modm).上述命题翻译成剩余类的语言，即指推论2.5.2模m的完全剩余系Zm上有自然诱导的加减乘运算(1)加法:a+b:=a+b,(2)减法：a-b:=a-b(3)乘法：a.b:=ab.如果(m,a)=1，则还有求乘法逆元的运算：(4) -1 := a-1这些运算不依赖于剩余类的代表元选取例2.5.2模3的剩余类有0，1,2.我们有以下的剩余类加法和乘法表+0120i12X000200011R11201012I2201210121此外，2-1=2,1-1=1,但0没有乘法逆元-推论2.5.3设k,l,meZ,且(k,m)=1. 设ao,ai,...,am-1是模m的完全剩余系，那么kao +7, ka1 +7, .,kam-1 +1也是模m的完全剩余系证明我们只需要证明诸kai+7两两不相同即可.首先注意（k，m）=1，因而下-1存在假设kai+/=kaj+1,则由a-aj=ai-aj=K-1.k(ai-a)=K-1.(kai+7-kaj+)=0- 22 -
第二章一次不定方程-这就证明了i=j，因而诸kai+两两不相同2.5.2既约剩余类与欧拉定理设a是模m的剩余类，如果（a,m）=1，则称a是与模m互质的剩余类.由命题2.5.2(3)，上述定义不依赖于代表元α的选取．所有与模m互质的剩余类全体构成的集合称作既约剩余系（有时也称为简化剩余系），记为Zm.显然ZmCZm与模m互质的剩余类个数记作m)，它可以看成㎡的函数，称为欧拉函数，我们也可以按如下方式等价定义欧拉函数定义2.5.2(m)就是指不超过m，且与m互素的正整数个数例2.5.3(1)取m=2,则既约剩余系 Zm=[1),(2)=1(2)取m=6,则既约剩余系Zm=[1,5],g(6)=2.(3)取m=10,则既约剩余系Zm=(1,3,7,9),(10)=4.-(4)取m=p是素数，则既约剩余系Zm=[I,2,,p-T)=Zm-[0),(p)=p-1.前面讨论过，Z㎡有诱导的加法和乘法运算，但是该加法运算对Z*不是封闭的.比如模3的既约剩余系={1,2],显然2=命题2.5.3模m的既约剩余系Zm关于乘法封闭，并且对任何aEZm，都有存在逆元a-lEZm.换言之，Zm是乘法群，特别地，Zm上可以定义除法运算，证明任取a,beZm，由定义知(a,m）=(b,m）=1.因此由消去律立得(ab,m)=1,即ab=abeZm.由命题2.5.2(5)，存在a的逆元aEZm，满足aa三1(modm)，因而m|(aa-1).设-d=(a,m)，则d/(ar-1)推出d|1,即d=1.这表明eZm例2.5.4考虑Zo上的乘法表×13719113719339177193997i13事实上，可以验证Z10是由3生成的循环群：具体言之，1=30=34,3=31,9=32,7=33．类似推论2.5.3，我们有以下结论推论2.5.4设k,mEZ,且(k,m)=1.设ai,a2,,ap(m)是模m的既约剩余系，那么kai,ka2,..., kap(m)也是模m的既约剩余系- 23 -
第二章一次不定方程证明与推论2.5.3的证明类似，我们可推出诸ka；两两不相同.因此剩下只需证明ka是-与模m互质的剩余类。这是显然的，因为(k,m)=(ai,m)=1,所以(kai,m)=1.定理2.5.1(欧拉定理）设k,mEZ,m>0,且(k,m)=1,则k:s(m) = 1 (mod m).换言之，对任何kEZm，都有(m)=1.证明月考虑模m的既约剩余系ai,a2,:,ap(m)由推论2.5.4kai,ha2, ..,kap(m)也是模㎡m的既约剩余系.这就推出0(m)s(m)II kai= l ai(mod m)i=1i=1因为（ai,m）=1,所以由消去律及上式即得(m)k:0(m) =II k=1 (mod m).i=1■这就完成了证明，注2.5.2我们也可以从群论的角度去证明上述的欧拉定理。由命题2.5.3，Z是乘法群，它的阶数等于(m).根据有限群的简单结果即得a(m)=1.-推论2.5.5（费马小定理）设p是素数，则对任何kEZ,都有kP=k(modp)证明如果(k,p)=1(即p+k),则在定理2.5.1中取m=p即得kp-1 =1 (mod p),即kP=k(modp)■如果p|k,即k=0 (mod p),则结论是显然的.注2.5.3我们后面将证明：对任何素数p，模p的既约剩余系Z=Z，一{0}是循环群。■推论2.5.6设k,mEZ，m>0，且(k,m）=1，则k(m)-1在模m下是k的逆元，即K-1 = ko(m)-1 e Zm.推论2.5.7设k,n,meZ, m>0, (m,k)=1. 设n=o(m)q+r (0≤r<q-1)是n除以<p(m）的带余数除法，则k"=k(mod m).证明k" = h:(m)a+r = (k9(m)g . k" = k" (mod m).- 24 -
第二章一次不定方程2.5.3一些简单的应用这里我们例举一些和同余有关的计算题以及相关的应用。例2.5.5（1）求3在模10下的逆元因为(10)=4，所以由推论2.5.6得3-1= 3(10)-1=33=7 (mod 10).(2)求13在模17下的逆元，因为17是素数，故(17)=16，所以由推论2.5.6得13-1=3(17)-1=1315= (-4)15=-4·414=-4·167=-4·(1)7=4(mod 17)例2.5.6设p是奇素数(1)求最小的正整数，使得2a三1(modp)利用带余数除法的唯一性，我们相当于要求正整数<P使得= 2-1 = 2P-2 (mod p)：由费马小定理知2p-1=1=1+p（modp).注意到1+p是偶数，所以由消去律得2P-2=P+1(mod p)2因此有=(2)设p>3,求最小的正整数a，使得3a=1(modp)由费马小定理知3p-1 =1=1+kp (mod p).这里『1,如果p=2(mod3)k=12,如果p=1(mod 3)显见3|1+kp.注意到(3,p）=1,故由消去律可得=3-1=3P-2=1+kp(mod p),3因而=服（1）求3103的末位数例2.5.7这相当于求最小正整数，使得三3103（mod10).注意到4(10)=4，所以由推论2.5.7,3103=34×25+3=33=7(mod10)。因此末尾数=7(2）求2103的末位数这相当于求最小正整数，使得&=2103（mod10).此时(2.10)=2，因而不能直接使用推论2.5.7.但我们注意到24h=(24)h=6h=6(mod10)，VkEZ+所以2103=24x25+3=6.23=8(mod10)- 25 -
第二章一次不定方程因此末尾数=8(3)求最小的正整数，使得三551°（mod7).因(7）=6,所以由推论2.5.7，我们要先求最小的正整数r，使得r=510（mod6).显见(r =(-1)10 = 1 (mod 6)-即r=1.这样，我们有三5"=5（mod7)，即a=5例2.5.8（（1）证明：n5+n3+n是整数这等价于证明15|3m5+5m3+7m.我们先证33m5+5m3+7m.此时3n5+ 5n3+7n = 5n3+7n = 2n3-2n =2(n3- n)= 0(mod 3).上式最后一步使用了费马小定理。其次证明5|3n5+5n2＋7n.此时3n5+5n3+7n=3n5+7n=3n5-3n=3(n§-n)=0(mod5)这就完成了证明，(2)证明：24|n(n+1)(n+2)(n+3).我们先证明3|n(n+1)(n+2)(n+3).此时n(n+1)(n+2)(n+3)=n(n+1)(n-1)n三n2(n2-1)=n(n3-n)=0(mod3)其次证明8|n(n+1)(n+2)n+3).如果n=2m，则n(n+1)(n+2)(n+3)=4m(m+1)(2m+1)(2m+3)注意到2|m(m+1),即得结论.如果n是奇数，则利用n2三1（mod8）得n(n + 1)(n +2)(n +3) = (n2 + 2n)(n2 + 4n +3) = 4(1 + 2n)(n +1) = 0 (mod 8).■上式最后一步用到2|n+1.以下我们介绍同余在p进位制表达中的应用.设a,pEZ*,p>1.考虑a的p进位制表达式a=anp"+an-ipn-1+...+aip+ao,0<ai≤p-1,i=1,2,.,n.有时也简记做a=(anan-1..aiao)p设sp(a) :=an +an-1+.+a1+a0,它称作a在p进位制下的位数码和比如27= (128)10= (10000000)2因此 810(27)=1+2+8=11,82(27)=1.日常生活中最常见的是十进制表达，但在计算机中则以二进制表达为主，为方便起见，当我们考虑十进制时，省略下标10以及上划线，即仍采用通常的写法- 26 -