初等数论 第四章 同余式.docx

初等数论 第四章 同余式第四章 同余式 第四章 同余式 §1 基本概念及一次同余式 初等数论中的一个基本课题是研究同余式的求解问题。定义1设mÎZ+，f(x)=anxn+an-1xn-1+L+a0，其中aiÎZ，则f(x)º0(modm)称为模m的同余式。若anº/0(modm)，则n称为次数。定义2若a是使f(a)º0(modm)成立的一个整数，则xºa(modm)叫做 f(x)º0(modm)的一个解。定义2的合理性：若f(a)º0(modm)，则剩余类Ka中的任意整数a¢都能使f(a¢)º0(modm)成立，故把Ka中的一切数，即xºa(modm)作为一个解。定理设(a,m)=d，则一次同余式axºb(modm)有解的充分必要条件是d|b。当此条件成立时，同余式共有d个解，它们是xºx0+k×m(modm)，k=0,1,L,d-1，d其中x0是同余式axºb(modm)的任一个解。证明(1)同余式axºb(modm)有解Û不定方程ax+my=b有解Ûd|b。(2)因为不定方程ax+my=b的一切整数解为x=x0+同余式axºb(modm)的解为xºx0+k×mt，tÎZ，所以，dm(modm)，k=0,1,L,d-1，解数为d。d注当(a,m)=1时，一次同余式有唯一解xºaj(m)-1b(modm)。 同余式的解法 1、代入法 例1解同余式3xº1(mod17)解因为(3,17)=1，所以同余式有唯一解， 以17的完全剩余系逐一代入，得xº6(mod17)。- 1 - 第四章 同余式 2、公式法 例2解同余式8xº9(mod11)解因为(8,11)=1，所以同余式有唯一解，从而，xº8j(11)-1×9º810-1×9º(-3)9×(-2)º(-2)4×6º5×6º8(mod11)。3、变换系数法 例3解下列同余式(1)4xº1(mod15)；(2)14xº27(mod31)；(3)103xº57(mod211)。解(1)因为(4,15)=1，所以同余式有唯一解，而4xº1º16(mod15)，故xº4(mod15)。(2)因为(14,31)=1，所以同余式有唯一解，而14xº27º58(mod31)，7xº29º60º91(mod31)，故xº13(mod31)。(3)因为(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)方便，而且若y0是(2)的解，则x0=b+my0是(1)的解。a- 2 - 第四章 同余式 例4解同余式863xº880(mod2151)解因863是质数，且863/|2151，故(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)，所以u0=1，z0=6+85×1-176+863×7880+2151×69=7，y0=69，x0=173，1385863即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)=3|15，所以同余式有3个解，由原同余式可得2xº5(mod11)，解得xº8(mod11)，因此原同余式的解为xº8，19，30(mod33)，。- 3 - 第四章 同余式 §2 孙子定理 本节讨论同余式组xºb1(modm1)，xºb2(modm2)，L，xºbk(modmk)的求解问题。 定理1设m1,m2,L,mk是两两互质的正整数，m=m1m2Lmk，m=miMi，i=1,2,L,k，则同余式组xºbk(modmk)的解是xºb1(modm1)，xºb2(modm2)，L，¢¢¢xºM1M1b1+M2M2b2+L+MkMkbk(modm)，¢其中MiMiº1(modmi)，i=1,2,L,k。证明因为(mi,mj)=1，i¹j，所以(mi,Mi)=1，于是¢¢有一解，设为Mi，则MiMiº1(modmi)，i=1,2,L,k，又因为m=miMi，所以mj|Mi，i¹j，于是故¢¢¢¢M1M1b1+M2M2b2+L+MkMkbkºMiMibiºbi(modmi)，¢¢¢xºM1M1b1+M2M2b2+L+MkMkbk(modm)是原同余式组的解。若x1,x2是适合同余式组的任意两个整数，则x1ºx2(modmi)，i=1,2,L,k，于是因此，原同余式组只有一个解x1ºx2(modm)，¢¢¢xºM1M1b1+M2M2b2+L+MkMkbk(modm)。Mixº1(modmi)推论1设正整数m1,m2,L,mk两两互质，则同余式组a1xºb1(modm1),a2xºb2(modm2),L,akxºbk(modmk)有解的充分必要条件是同余式aixºbi(modmi)，i=1,2,L,k有解。证明必要性是显然的，下证充分性。因为对i=1,2,L,k，同余式aixºbi(modmi)，所以di|bi，这里di=(ai,mi)，于是有ci使xºc1aimciº1(modi)，从而原同余式组等价于didibmb1mbm(mod1),xºc22(mod2),L,xºckk(modk)，当然有解。d1d1d2d2dkdk- 4 - 第四章 同余式 推论2若b1,b2,L,bk分别通过模m1,m2,L,mk的完全剩余系，则¢¢¢xºM1M1b1+M2M2b2+L+MkMkbk(modm)通过模m=m1m2Lmk的完全剩余系。¢证明令x0=åMiMibi，则x0过m1m2Lmk个数，这m个数两两不同余。 i=1k这是因为若åMi=1k¢i¢²MibiºåMiMibi(modm)，i=1¢k¢¢¢²¢²则MiMibiºMiMibi(modmi)，即biºbi(modmi)，i=1,2,L,k，矛盾。 定理1之所以称为“孙子定理”，因为在我国古代的数学著作孙子算经中已经提出了这种形式的问题，并且很好地解决了它。孙子定理在国外文献和教科书中均称为“中国剩余定理”，并且在代数学中被推广成非常一般的形式。 孙子算经中所提出的问题之一如下：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。 用现在的记号，上述问题相当于求解同余式组 xº2(mod3)，xº3(mod5)，xº2(mod7)。 孙子算经中所用的方法可以列表如下： 除数 余数 最小公倍数 衍数 乘率 3 5 7 2 3 2 3×5 ×7=105 5×7 7×3 3×5 2 1 1 各 总 35×2×2 21×1×3 15×1×2 140+63 +30=233 233- 105×2=23 答数 最 小 答 数 程大位在算法统宗中将这一问题的算法总结成如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。 推广为一般的列表算法： - 5 - 第四章 同余式 除数 余数 最小公倍数 衍数 乘率 m1 m2 mk b1 b2 bk m=m1m2mk M1 M2 Mk M1 M2 Mk 各 总 M1M1b1 M2M2b2 MkMkbk 答数 xºåMiMi'bi(modm) i=1k例1解同余式组xºb1(mod5),xºb2(mod6),xºb3(mod7),xºb4(mod11)。解m=5×6×7×11=2310，M1=6×7×11=462，M2=5×7×11=385，M3=5×6×11=330，M4=5×6×7=210，解同余式¢¢462M1º1(mod5)得M1=3¢¢385M2º1(mod6)得M2=1¢¢330M3º1(mod5)得M3=1¢¢210M4º1(mod5)得M4=1因此同余式组的解为xº3×462×b1+1×385×b2+1×330×b3+1×210×b4(mod2310)。例2韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人。求兵数。解设兵数为x，则xº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ºbi(modmi)，i=1,2,L,k有解的充分必要条件是biºbj(mod(mi,mj)，i¹j=1,2,L,k。若上述条件成立，则同余式组对模m1,m2,L,mk有唯一解。- 6 - 第四章 同余式 例3解同余式组xº8(mod15),xº3(mod10),xº1(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)得代入得xº23(mod30)。xº23(mod30),xº1(mod8)，xº113(mod120)。yº1(mod2)，再解同余式组可得原同余式组的解是另解原同余式组可化为ìxº8(mod5)ïxº8(mod3)ïïíxº3(mod5)，即ïxº3(mod2)ï3ïîxº1(mod2)由孙子定理可解得ìxº3(mod5)ïíxº2(mod3) ïxº1(mod23)îxº113(mod120)。- 7 - 第四章 同余式 §3 质数模的同余式 本节讨论质数模的同余式(1)f(x)º0(modp)，其中f(x)=anxn+an-1xn-1+L+a0，p为质数，anº/0(modp)。定理1同余式(1)与一个次数不超过p-1的质数模同余式等价。证明由多项式的带余除法可知f(x)=(xp-x)q(x)+r(x)，¶(r(x)£p-1，f(x)ºr(x)(modp)，由费马定理可知，"xÎZ，有xp-xº0(modp)，于是因此，同余式(1)与r(x)º0(modp)等价。定理2设k£n，而xºai(modp)，i=1,2,L,k是(1)的k个不同的解，则"xÎZ，f(x)º(x-a1)(x-a2)L(x-ak)fk(x)(modp)，其中fk(x)是一个n-k次多项式，首项系数为an。证明由多项式的带余除法可知f(x)=(x-a1)f1(x)+r，其中f1(x)是一个首项系数为an的n-1次多项式，r是一个常数，因为f(ai)º0(modp)，所以rº0(modp)，于是f(x)º(x-a1)f1(x)(modp)，令x=ai，i=2,3,L,k，则0º(ai-a1)f1(ai)(modp)，又aiº/a1(modp)，p为质数，故f1(ai)º0(modp)，从而由归纳法可得结论。定理3(1)"xÎZ，xp-1-1º(x-1)(x-2)L(x-(p-1)(modp)；(2)(Wilson 定理)(p-1)!+1º0(modp)。证明(1)因为(i,p)=1，i=1,2,L,p-1，所以由欧拉定理可知1,2,L,p-1都是xp-1-1º0(modp)的解，于是由定理2可知xp-1-1º(x-1)(x-2)L(x-(p-1)fk(x)(modp)，fk(x)为零次多项式，首项系数为1，即xp-1-1º(x-1)(x-2)L(x-(p-1)(modp)。(2)在(1)中令x=0，则(-1)(-2)L(-(p-1)º-1(modp)，当p=2时，结论显然成立；当p为奇质数时，(p-1)!+1º0(modp)。- 8 - 第四章 同余式 定理4同余式(1)的解数不超过它的次数。证明设(1)的解数超过n，则(1)至少有n+1个解，设为xºai(modp)，i=1,2,L,n+1，于是由定理2可知f(x)ºan(x-a1)(x-a2)L(x-an)(modp)，又f(an+1)º0(modp)，故an(an+1-a1)(an+1-a2)L(an+1-an)º0(modp)，又因p为质数，anº/0(modp)，故必存在ai，i=1,2,L,n，有ai=an+1(modp)，矛盾，因此，结论成立。定理5若n£p，则同余式(1)有n个解的充分必要条件是f(x)除xp-x所得余式的一切系数都是p的倍数。证明由多项式的带余除法可知xp-x=f(x)q(x)+r(x)，¶(r(x)<n，若(1)有n个解，则由费马定理可知这n个解都是xp-xº0(modp)的解，于是这n个解也是r(x)º0(modp)的解，但¶(r(x)<n，故由定理4可知r(x)的系数都是p的倍数。反之，若r(x)的系数都是p的倍数，则由费马定理可知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)=anxn+an-1xn-1+L+a0º0(modp)，a的具体解法： 1、简化同余式，一般考虑以下简化方法： (1)若f(x)的系数中有大于p的数，则可将其化到小于p； nºp)/0(mod(2)若¶(f(x)>p，则可用xp-x去除f(x)，则可得到一个次数较低的与原同余式等价的同余式； (3)若f(x)关于模p有一个或几个因式，则也可将原同余式的次数降低； (4)若f(x)已知有一解或几解，则可析出因式将次数降低。 2、将模的完全剩余系中的数逐一代入同余式，检验即可得解。 - 9 - 第四章 同余式 例解同余式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)与原同余式等价，xº-1,1,2(mod5)。将模5的完全剩余系-2,-1,0,1,2逐一代入，知原同余式的解是- 10 - 第四章 同余式 §4 高次同余式的解法 定理1(1)设m1,m2,L,mk是k个两两互质的正整数，m=m1m2Lmk，则同余式f(x)º0(modm)与同余式组f(x)º0(modmi)，i=1,2,L,k等价；(2)若Ti表示f(x)º0(modmi)对模mi的解数，i=1,2,L,k，T表示同余式f(x)º0(modm)对模m的解数，则T=T1T2LTk。证明(1)设x0是f(x)º0(modm)的解，则f(x0)º0(modm)，由同余性质6可知f(x0)º0(modmi)，i=1,2,L,k；反之，若x0是同余式组f(x)º0(modmi)，i=1,2,L,k的解，则f(x0)º0(modmi)，i=1,2,L,k，由同余性质5可知f(x0)º0(modm)。因此，同余式f(x)º0(modm)与同余式组f(x)º0(modmi)，i=1,2,L,k等价。(2)设f(x)º0(modmi)的Ti个不同的解为xºbiti(modmi)，ti=1,2,L,Ti，i=1,2,L,k，则同余式组f(x)º0(modmi)，i=1,2,L,k的解即为下列同余式组的解xºb1t1(modm1),xºb2t2(modm2),L,xºbktk(modmk)，ti=1,2,L,Ti，i=1,2,L,k，共有T1T2LTk个同余式组，由孙子定理可知，每个同余式组对模m恰有一解，故有T1T2LTk个解，并且由孙子定理之推论2可知这T1T2LTk个解对模m两两不同余，因此，f(x)º0(modm)的解数为T1T2LTk。例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)。- 11 - 第四章 同余式 定理2设xºx1(modp)，即x=x1+pt1，t1ÎZ是f(x)º0(modp)的一解，并且p/|f¢(x1)，则x=x1+pt1恰好给出了f(x)º0(modpa)的一解(对模pa来说)：x=xa+pata，taÎZ，即xºxa(modpa)，其中xaºx1(modp)。证明对a作数学归纳法。当a=2时，要求由x=x1+pt1给出f(x)º0(modp2)的一解，也即要求满足f(x1+pt1)º0(modp2)的t1。由泰勒展开可知于是t1f¢(x1)º-f(x1)+pt1f¢(x1)º0(modp2)，f(x1)(modp)，p¢¢¢因为p/|f1(x)，即(p,f1(x)=1，所以同余式对模p有唯一解：t1ºt1(modp)，¢即t1=t1+pt2，t2ÎZ，代入x=x1+pt1得¢x=x1+p(t1+pt2)=x2+p2t2，t2ÎZ，其中x2ºx1(modp)。假设结论对之情形成立，即x=x1+pt1恰好给出了f(x)º0(modpa-1)的一解：x=xa-1+pa-1ta-1，ta-1ÎZ，xa-1ºx1(modp)，将其代入f(x)º0(modpa)由泰勒展开，得f(xa-1)+pa-1ta-1f¢(xa-1)º0(modpa)，于是ta-1f¢(xa-1)º-f(xa-1)(modp)，pa-1因为xa-1ºx1(modp)，所以f¢(xa-1)ºf¢(x1)(modp)，从而p/|f¢(xa-1)，¢¢故上面同余式有唯一解：ta-1ºta-1(modp)，即ta-1=ta-1+pta，taÎZ，代入x=xa-1+pa-1ta-1得f(x)º0(modpa-1)的一解：¢x=xa-1+pa-1(ta-1+pta)=xa+pata，taÎZ，其中xaºx1(modp)。因此，结论普遍成立。- 12 - 第四章 同余式 例2解同余式f(x)=x4+7x+4º0(mod27)。解首先求得f(x)º0(mod3)的解为xº1(mod3)，并且f¢(1)º/0(mod3)；将x=1+3t1代入f(x)º0(mod9)得到f(1)+3t1f¢(1)º0(mod9)，即3+6t1º0(mod9)，解得t1º1(mod3)， 令t1=1+3t2，则x2=1+3t1=1+3(1+3t2)=4+9t2是f(x)º0(mod9)的一解；将x2=4+9t2代入f(x)º0(mod27)得到f(4)+9t2f¢(4)º0(mod27)，即18+180t2º0(mod27)，解得t2º2(mod3)，令t2=2+3t3，则x3=22+27t3是f(x)º0(mod27)的一个解，因此，原同余式的解为例3解同余式xº22(mod27)。f(x)=x3-2x+6º0(mod53)。解首先求得f(x)º0(mod5)有两个解：xº1,2(mod5)。先讨论x1º1(mod5)，将x1=1+5t1代入f(x)º0(mod52)得f(1)+5t1f¢(1)º0(mod52)，即5+5t1º0(mod52)，解得t1º-1(mod5)，令t1=-1+5t2，则x2=-4+25t2，将x2=-4+25t2代入f(x)º0(mod53)得f(-4)+25t2f¢(-4)º0(mod53)，即-50+25×46t2º0(mod53)，x3=46+125t3，即xº46(mod53)解得t2º2(mod5)，令t2=2+5t3，则是f(x)º0(mod53)的一个解；¢¢再讨论x1º2(mod5)，将x1=2+5t1代入f(x)º0(mod52)得f(2)+5t1f¢(2)º0(mod52)，即10+50t1º0(mod52)，此同余式无解；xº46(mod53)。因此，原同余式的解为解法总结：aka1a2"mÎZ+，m=p1p2Lpk，要解同余式f(x)º0(modm)，只需解 f(x)º0(modpiai)，i=1,2,L,k，从而转化为解质数模的同余式。- 13 -