初等数论第四章同余式

第四章同余式§1基本概念及一次同余式初等数论中的一个基本课题是研究同余式(同余方程)的求解问题。定义1设meZ+,f(x)=a其中aeZ,贝I」nn-10if(x)三0(modm)称为模m的同余式。若a丰0(modm),贝肮称为次数。n定义2若a是使f(a)三0(modm)成立的一个整数，则x三a(modm)叫做f(x)三0(modm)的一个解。定义2的合理性：若f(a)三0(modm)，则剩余类K中的任意整数a，都能使af(a')三0(modm)成立，故把K中的一切数，即x三a(modm)作为一个解。a定理设(a,m)=d则一次同余式ax三b(modm)有解的充分必要条件是dIb。当此条件成立时，同余式共有d个解，它们是x三x三x+k-m(modm)，0dk=0,1,…,d—1,其中x是同余式ax三b(modm)的任一个解。0证明⑴同余式ax三b(modm)有解o不定方程ax+my=b有解odIb。⑵因为不定方程ax+my=b的一切整数解为x=x+mt，teZ,所以,同余式解数为d。同余式解数为d。ax三b(modm)的解为x三x+k—(modm),k=0,1,…,d—1,

0d注当(a,m)=1时，一次同余式有唯一解x三a車«)-ib(modm)。同余式的解法1、代入法(适用于模较小时)例1解同余式3x三1(mod17)解因为(3,17)=1,所以同余式有唯一解，以17的完全剩余系逐一代入，得x三6(modl7)。2、公式法(适用于模较小时)例2解同余式8x三9(mod11)解因为(8,11)=1，所以同余式有唯一解，从而，x三8車11)-1•9三810-1•9三(-3)9-(一2)三(-2)4-6三5-6三8(mod11)。3、变换系数法例3解下列同余式4x三1(mod15)；14x三27(mod31)；103x三57(mod211)。解⑴因为(4,⑸=1,所以同余式有唯一解，而4x三1三16(mod15)，故x三4(mod15)。(2)因为(14,31)=1,所以同余式有唯一解，而14x三27三58(mod31)，7x三29三60三91(mod31)，故x三13(mod31)。⑶因为(103,211)=1,所以同余式有唯一解，由103x三57(mod211)可得206x三114(mod211)，于是—5x三114(mod211)即5x三97(mod211)，再由5x三97(mod211)可得210x三97-42(mod211)，于是—x三97-42三65(mod211)故x三-65三146(mod211)。

4、换模法由ax三b(modm)(1)可得ax=b+my,模a后可得my三-b(moda)(2),当0<a<m时，解(2)比解(1)方便，而且若y是(2)的解，贝吐=耳竺是(1)的解。00a例4解同余式863x三880(mod2151)解因863是质数，且863J2151，故(863,2151)=1,从而同余式有唯一解,原同余式可化为863x=880+2151y，模863后得2151y三-880(mod863),即425y三-880(mod863),也即85y三—176(mod863),再化为85y=—176+863z，模85后得863z三176(mod85),即13z三6(mod85),再化为13z=6+85u，模13后得85u三一6(mod13),即7u三7(mod13),也即u三1(mod13),所以u=1所以u=1,06+85-1—176+863-7“z==7,y==69,013085880+2151•69863即x三173(mod2151)是原同余式的解。5、辗转相除法例5解同余式863x三880(mod2151)解因为(863,2151)=1,所以同余式有唯一解利用辗转相除法可得-496•863+199•2151=1,模2151后得—496•863三1(mod2151),所以x三—496・880三173(mod2151)。例6解同余式6x三15(mod33)解因为(6,33)=3115,所以同余式有3个解，由原同余式可得2x三5(mod11),解得x三8(mod11),因此原同余式的解为x三8,19,30(mod33),。§2孙子定理本节讨论同余式组x三b(modm),x三b(modm),•••,x三b(modm)1122kk的求解问题。定理1(孙子定理)设m,m，…,m是两两互质的正整数，m=mm…m,12k12km=mM,i=1,2,…,k,则同余式组x三b(modm),x三b(modm),•••,TOC\o"1-5"\h\zii1122x三b(modm)的解是x三MMb+MMbHbMMb(modm),kk111222kkk其中MM三1(modm),i=1,2,…,k。iii证明因为(m,m)=1,i丰j所以(m,M)=1,于是Mx三1(modm)ijiiii有一解，设为M，贝9MM三1(modm),i=1,2,…,k,iiii又因为m=mM，所以mIM,i丰jiijirrrf于是MMb+MMbHbMMb三MMb三b(modm),111222kkkiiiii故x三MMb+MMb+…+MMb(modm)是原同余式组的解。111222kkk若x,x是适合同余式组的任意两个整数，12贝9x三x(modm),i=1,2,…，k,于是x三x(modm),12i12fff因此，原同余式组只有一个解x三MMb+MMb+—bMMb(modm)。111222kkk推论1设正整数m,m，…,m两两互质，则同余式组12kax三b(modm),ax三b(modm),•…,ax三b(modm)111222kkkTOC\o"1-5"\h\z有解的充分必要条件是同余式ax三b(modm),i=1,2,…,k有解。iii证明必要性是显然的，下证充分性。因为对i=1,2,…,k，同余式ax三b(modm)，所以dIb，这里d=(a,m)，iiiiiiii于是有ci使”三1(mod沪，从而原同余式组等价于iix三c廿(modi),x三c犷(mod1x三c廿(modi),x三c犷(mod1dd2d1122kk推论2若b,b,…,b分别通过模m,m,…,m的完全剩余系，则12k12kfffx三MMb+MMbHFMMb(modm)111222kkk通过模m=mm…m的完全剩余系。12k证明令x=工MMb，贝Ijx过mm…m个数，这m个数两两不同余。0iii012k这是因为若工M‘M这是因为若工M‘Mbiiii=1ZffMMb(modm)，

iiii=1i=1,2,…,k,i=1,2,…,k,矛盾。则MMb三MMb(modm)，即b三b(modm)，iiiiiiiiii定理1之所以称为“孙子定理”，因为在我国古代的数学著作《孙子算经》(纪元前后)中已经提出了这种形式的问题，并且很好地解决了它。孙子定理在国外文献和教科书中均称为“中国剩余定理”，并且在代数学中被推广成非常一般的形式。孙子算经》中所提出的问题之一如下：今有物不知其数，三三数之剩二，

五五数之剩三，七七数之剩二，问物几何答曰：二十三。用现在的记号，上述问题相当于求解同余式组x三2(mod3),x三3(mod5),x三2(mod7)。孙子算经》中所用的方法可以列表如下：除数余数最小公倍数衍数乘率各总答数最小答数323X5X7=1055X7235X2X2140+63+30=233233-105X2=23537X3121X1X3723X5115X1X2程大位在《算法统宗》(1593)中将这一问题的算法总结成如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。推广为一般的列表算法：除数余数最小公倍数衍数乘率各总答数m1b1m二吧…mkM1M'1MM'b111x三乞MM'b(modm)iiir=11

12341234解m=5-6-7-11=2310,M=6-7-11=462,M=5-7-11=385,12M二5・6・11二330,M二5・6・7二210,34f得f得M=31f得M=12f得M=13f得M=14解同余式462M三1(mod5)1f385M三1(mod6)2f330M三1(mod5)3f210M三1(mod5)4因此同余式组的解为x三3-462-b1+1-385-b+1-330-b+因此同余式组的解为x三3-462-b1234例2韩信点兵：有兵一队,若列成五行纵队,则末行一人,成六行纵队,则末行五人,成七行纵队,则末行四人,成十一行纵队,则末行十人。求兵数解设兵数为x,贝Vx三1(mod5),x三5(mod6),x三4(mod7),x三10(mod11)故解为x三3-462-1+1-385-5+1-330-4+1-210-10三6731三2111(mod2310)。定理2同余式组x三b(modm),i=1,2,…,k有解的充分必要条件是iib三b(mod(m,m)),i丰j=1,2,…,k。ijij若上述条件成立，则同余式组对模［m,m,…,m］有唯一解。12k例3解同余式组x三8(mod15),x三3(mod10),x三l(mod8)。解因为8三3(mod(15,10)),8三1(mod(15,8)),3三1(mod(10,8)),所以同余式组有唯一解。先解同余式组x三8(mod15),x三3(mod10)。由x三8(mod15)可矢口x=8+15y,代入x三3(mod10)得y三1(mod2),代入得x三23(mod30)。再解同余式组x三23(mod30),x三1(mod8),可得原同余式组的解是x三113(mod120)。另解原同余式组可化为x三8(mod5)x三3(mod5)<x三x三3(mod5)<x三2(mod3)x三1(mod23)<x三3(mod5)，即x三3(mod2)x三1(mod23)由孙子定理可解得x三113(mod120)。§3质数模的同余式本节讨论质数模的同余式(1)f(x)三0(modp),其中f(x)=axn+axn-ihba,p为质数，a丰0(modp)。nn-10n定理1同余式⑴与一个次数不超过p-1的质数模同余式等价。证明由多项式的带余除法可知f(x)=(xp-x)q(x)+r(x)，d(r(x))<p-1,由费马定理可知，VxgZ,有xp一x三0(modp),于是f(x)三r(x)(modp)，因此，同余式⑴与r(x)三0(modp)等价。定理2设k<n,而x=a(modp),i=1,2,…,k是⑴的k个不同的解，贝ViVxgZ,f(x)三(x-a)(x-a)…(x-a)f(x)(modp),其中f(x)是一个n—k12kkk次多项式，首项系数为a。n证明由多项式的带余除法可知f(x)=(x-a)f(x)+r,其中f(x)是一111个首项系数为a的n-1次多项式，r是一个常数，n因为/(a)三0(modp),所以r三0(modp),于是f(x)三(x-a)f(x)(modp),TOC\o"1-5"\h\zi11令x=a,i=2,3,…,k,贝U0三(a-a)f(a)(modp),ii11i又a羊a(modp),p为质数，故f(a)三0(modp\从而由归纳法可得结论。i11i定理3(1)VxgZ,xp-1一1三(x一1)(x一2)…(x-(p一1))(modp)；(2)(Wilson定理)(p一1)!+1三0(modp)。证明⑴因为(i,p)=1,i=1,2,…,p-1,所以由欧拉定理可知1,2,…,p-嘟是xp-1-1三0(modp)的解，于是由定理2可知xp-1一1三(x一1)(x一2)…(x-(p一1))f(x)(modp),f(x)为零次多项式，kk首项系数为1,即xp-1一1三(x一1)(x一2)…(x-(p一1))(modp)。(2)在(1)中令x=0,贝9(-1)(-2)…(-(p一1))三一1(modp),当p=2时，结论显然成立；当p为奇质数时，(p-1)!+1三0(modp)。定理4同余式(1)的解数不超过它的次数。证明(反证法)设⑴的解数超过n,则⑴至少有n+1个解，设为x=a(modp),i=1,2,…,n+1,于是由定理2可知if(x)三a(x-a)(x-a)…(x-a)(modp)，n12n又f(a)三0(modp),故a(a-a)(a-a)…(a-a)三0(modp)，n十1nn十11n十12n十1n又因p为质数，a=0(modp),故必存在a，i=1,2,…,n,有a=a(modp)，niin十1矛盾，因此，结论成立。定理5若n<p,则同余式⑴有n个解的充分必要条件是f(x)除xp-x所得余式的一切系数都是p的倍数。证明由多项式的带余除法可知xp-x=f(x)q(x)+r(x),d(r(x))<n,若⑴有n个解，则由费马定理可知这n个解都是xp-x三0(modp)的解，于是这n个解也是r(x)三0(modp)的解，但6(r(x))<n,故由定理4可知r(x)的系数都是p的倍数。反之，若r(x)的系数都是p的倍数，贝9由费马定理可知f(x)q(x)有p个不同的解(实际上是一切整数)，假设f(x)的解数小于n,而q(x)的解数小于等于p-n,于是f(x)q(x)三0(modp)的解数小于n+(p-n)=p,矛盾，故同余式有n个解。质数模同余式f(x)=axn+axn-i+…+a三0(modp),a=0(modp)nn-10n的具体解法：1、简化同余式，一般考虑以下简化方法：(1)若f(x)的系数中有大于P的数，则可将其化到小于P;⑵若6(f(x))>p，则可用xp-x去除f(x),则可得到一个次数较低的与原同余式等价的同余式；(3)若f(x)关于模p有一个或几个因式，则也可将原同余式的次数降低；⑷若f(x)已知有一解或几解，则可析出因式将次数降低。2、将模的完全剩余系中的数逐一代入同余式，检验即可得解。例解同余式f(x)=x7-2x6-7x5+x+2三0(mod5)。解化简系数，得x7一2x6-2x5+x+2三0(mod5),用x5-x去除，得r(x)=x3-2x2-x+2三0(mod5)与原同余式等价，将模5的完全剩余系-2,-1,0,1,2逐一代入，知原同余式的解是x三-1,1,2(mod5)。§4高次同余式的解法定理1⑴设m,m，…,m是k个两两互质的正整数，m=mm…m，贝V12k12k同余式f(x)三0(modm)与同余式组f(x)三0(modm),i=1,2,…,k等价；i(2)若T表示f(x)三0(modm)对模m的解数，i=1,2,…,k，T表示同余式iiif(x)三0(modm)对模m的解数，则T=TT-T。12k证明⑴设x是f(x)三0(modm)的解，则f(x)三0(modm)，00由同余性质6可知f(x)三0(modm)，i=1,2,…,k；0i反之，若x是同余式组f(x)三0(modm)，i=1,2,…,k的解，则0if(x)三0(modm)，i=1,2,…,k，由同余性质5可知f(x)三0(modm)。0i0因此，同余式/(x)三0(modm)与同余式组/(x)三0(modm)，i=1,2,…,k等价。i(2)设f(x)三0(modm)的T个不同的解为x三b(modm)，t=1,2,…,T，iiitiiiii=1,2,…,k,则同余式组f(x)三0(modm)，i=1,2,…,k的解即为下列同余式i组的解x三b(modm),x三b(modm)，…,x三b(modm)，t=1,2,…,T，TOC\o"1-5"\h\z1t12t2ktkii12ki=1,2,-,k,共有TT…个同余式组，由孙子定理可知，每个同余式组对12k模m恰有一解，故有TT…丁个解，并且由孙子定理之推论2可知这TT…T12k12k个解对模m两两不同余，因此，f(x)三0(modm)的解数为TT--T。12k例1解同余式f(x)=x4+2x3+8x+9三0(mod35)。解原同余式与同余式组f(x)三0(mod5),f(x)三0(mod7)等价，而同余式f(x)三0(mod5)的解为x三1,4(mod5)，同余式f(x)三0(mod7)的解为x三3,5,6(mod7)，故原同余式有6个解，它们分别是下列同余式组的解：x三1(mod5)[x三4(mod5)x三3,5,6(mod7)[x三3,5,6(mod7)由孙子定理可得6个解为：x三6,19,24,26,31,34(mod35)。定理2设x三x(modp),即x=x+pt,teZ是f(x)三0(modp)的一1111f解，并且pJf(x)，则x=x+pt恰好给出了f(x)三0(modpa)的一解(对模111pa来说)：x=x+pat,teZ,即卩x三x(modpa)，其中x三x(modp)。aaaaa1证明对a作数学归纳法。当a=2时，要求由x=x+pt给出f(x)三0(modp2)的一解，也即要求11满足f(x+pt)三0(modp2)的t。111由泰勒展开可知f(x)+ptf'(x)三0(modp2)，111于是tf'(x)三_""i)(modp)，11pfff因为pJf(x)，即(p,f(x))=1所以同余式对模p有唯一解：三t(modp)，1111f即t=t+pt，teZ，代入x=x+pt得112211fx=x+p(t+pt)=x+p21，teZ,其中x三x(modp)。11222221假设结论对之情形成立，即x=x+pt恰好给出了f(x)三0(modpa-1)的11一解：x=x+pa-it，teZ，x三x(modp)，TOC\o"1-5"\h\za-1a-1a-1a-11将其代入f(x)三0(modpa)由泰勒展开，得f(x)+pa-1tf'(x)三0(modpa)，a-1a-1a-1于是tf'(x)三-/""a-1)(modp)，a-1a-1pa-1,f因为x三x(modp)，所以f'(x)三f'(x)(modp),从而pJf(x)，a-11a-11a-1故上面同余式有唯一解:：三t(modp),即t=t+pt,teZ,a-1a-1a-1a-1aa代入x=x+pa-1t得f(x)三0(modpa-1)的一解：a-1a-1fx=x+pa-1(t+pt)=x+pat,teZ,其中x三x(modp)。a-1a-1aaaaa1因此，结论普遍成立。

例2解同余式f(x)=x