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

《初等数论 第四章 同余式.docx》由会员分享，可在线阅读，更多相关《初等数论 第四章 同余式.docx（18页珍藏版）》请在三一办公上搜索。

1、初等数论 第四章 同余式第四章 同余式 第四章 同余式 1 基本概念及一次同余式 初等数论中的一个基本课题是研究同余式的求解问题。定义1设mZ+，f(x)=anxn+an-1xn-1+L+a0，其中aiZ，则f(x)0(modm)称为模m的同余式。若an/0(modm)，则n称为次数。定义2若a是使f(a)0(modm)成立的一个整数，则xa(modm)叫做 f(x)0(modm)的一个解。定义2的合理性：若f(a)0(modm)，则剩余类Ka中的任意整数a都能使f(a)0(modm)成立，故把Ka中的一切数，即xa(modm)作为一个解。定理设(a,m)=d，则一次同余式axb(modm)有

2、解的充分必要条件是d|b。当此条件成立时，同余式共有d个解，它们是xx0+km(modm)，k=0,1,L,d-1，d其中x0是同余式axb(modm)的任一个解。证明(1)同余式axb(modm)有解不定方程ax+my=b有解d|b。(2)因为不定方程ax+my=b的一切整数解为x=x0+同余式axb(modm)的解为xx0+kmt，tZ，所以，dm(modm)，k=0,1,L,d-1，解数为d。d注当(a,m)=1时，一次同余式有唯一解xaj(m)-1b(modm)。 同余式的解法 1、代入法 例1解同余式3x1(mod17)解因为(3,17)=1，所以同余式有唯一解， 以17的完全剩余系

3、逐一代入，得x6(mod17)。- 1 - 第四章 同余式 2、公式法 例2解同余式8x9(mod11)解因为(8,11)=1，所以同余式有唯一解，从而，x8j(11)-19810-19(-3)9(-2)(-2)46568(mod11)。3、变换系数法 例3解下列同余式(1)4x1(mod15)；(2)14x27(mod31)；(3)103x57(mod211)。解(1)因为(4,15)=1，所以同余式有唯一解，而4x116(mod15)，故x4(mod15)。(2)因为(14,31)=1，所以同余式有唯一解，而14x2758(mod31)，7x296091(mod31)，故x13(mod31

4、)。(3)因为(103,211)=1，所以同余式有唯一解，由103x57(mod211)可得206x114(mod211)，于是-5x114(mod211)即5x97(mod211)，再由5x97(mod211)可得210x9742(mod211)，于是-x974265(mod211)故x-65146(mod211)。4、换模法 由axb(modm)(1)可得ax=b+my，模a后可得my-b(moda)(2)，当0am时，解(2)比解(1)方便，而且若y0是(2)的解，则x0=b+my0是(1)的解。a- 2 - 第四章 同余式 例4解同余式863x880(mod2151)解因863是质数，

5、且863/|2151，故(863,2151)=1，从而同余式有唯一解，原同余式可化为863x=880+2151y，模863后得2151y-880(mod863)，即425y-880(mod863)，也即85y-176(mod863)，再化为85y=-176+863z，模85后得863z176(mod85)，即13z6(mod85)，再化为13z=6+85u，模13后得85u-6(mod13)，即7u7(mod13)，也即u1(mod13)，所以u0=1，z0=6+851-176+8637880+215169=7，y0=69，x0=173，1385863即x173(mod2151)是原同余式的解

6、。 5、辗转相除法 例5解同余式863x880(mod2151)解因为(863,2151)=1，所以同余式有唯一解，利用辗转相除法可得-496863+1992151=1， 模2151后得-4968631(mod2151)，所以x-496880173(mod2151)。例6解同余式6x15(mod33)解因为(6,33)=3|15，所以同余式有3个解，由原同余式可得2x5(mod11)，解得x8(mod11)，因此原同余式的解为x8，19，30(mod33)，。- 3 - 第四章 同余式 2 孙子定理 本节讨论同余式组xb1(modm1)，xb2(modm2)，L，xbk(modmk)的求解问题

7、。 定理1设m1,m2,L,mk是两两互质的正整数，m=m1m2Lmk，m=miMi，i=1,2,L,k，则同余式组xbk(modmk)的解是xb1(modm1)，xb2(modm2)，L，xM1M1b1+M2M2b2+L+MkMkbk(modm)，其中MiMi1(modmi)，i=1,2,L,k。证明因为(mi,mj)=1，ij，所以(mi,Mi)=1，于是有一解，设为Mi，则MiMi1(modmi)，i=1,2,L,k，又因为m=miMi，所以mj|Mi，ij，于是故M1M1b1+M2M2b2+L+MkMkbkMiMibibi(modmi)，xM1M1b1+M2M2b2+L+MkMkbk(

8、modm)是原同余式组的解。若x1,x2是适合同余式组的任意两个整数，则x1x2(modmi)，i=1,2,L,k，于是因此，原同余式组只有一个解x1x2(modm)，xM1M1b1+M2M2b2+L+MkMkbk(modm)。Mix1(modmi)推论1设正整数m1,m2,L,mk两两互质，则同余式组a1xb1(modm1),a2xb2(modm2),L,akxbk(modmk)有解的充分必要条件是同余式aixbi(modmi)，i=1,2,L,k有解。证明必要性是显然的，下证充分性。因为对i=1,2,L,k，同余式aixbi(modmi)，所以di|bi，这里di=(ai,mi)，于是有c

9、i使xc1aimci1(modi)，从而原同余式组等价于didibmb1mbm(mod1),xc22(mod2),L,xckk(modk)，当然有解。d1d1d2d2dkdk- 4 - 第四章 同余式 推论2若b1,b2,L,bk分别通过模m1,m2,L,mk的完全剩余系，则xM1M1b1+M2M2b2+L+MkMkbk(modm)通过模m=m1m2Lmk的完全剩余系。证明令x0=MiMibi，则x0过m1m2Lmk个数，这m个数两两不同余。 i=1k这是因为若Mi=1kiMibiMiMibi(modm)，i=1k则MiMibiMiMibi(modmi)，即bibi(modmi)，i=1,2,

10、L,k，矛盾。 定理1之所以称为“孙子定理”，因为在我国古代的数学著作孙子算经中已经提出了这种形式的问题，并且很好地解决了它。孙子定理在国外文献和教科书中均称为“中国剩余定理”，并且在代数学中被推广成非常一般的形式。 孙子算经中所提出的问题之一如下：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。 用现在的记号，上述问题相当于求解同余式组 x2(mod3)，x3(mod5)，x2(mod7)。 孙子算经中所用的方法可以列表如下： 除数 余数 最小公倍数 衍数 乘率 3 5 7 2 3 2 35 7=105 57 73 35 2 1 1 各 总 3522 211

11、3 1512 140+63 +30=233 233- 1052=23 答数 最 小 答 数 程大位在算法统宗中将这一问题的算法总结成如下歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆半个月，除百零五便得知。 推广为一般的列表算法： - 5 - 第四章 同余式 除数 余数 最小公倍数 衍数 乘率 m1 m2 mk b1 b2 bk m=m1m2mk M1 M2 Mk M1 M2 Mk 各 总 M1M1b1 M2M2b2 MkMkbk 答数 xMiMibi(modm) i=1k例1解同余式组xb1(mod5),xb2(mod6),xb3(mod7),xb4(mod11)。解m=56711=2310

12、，M1=6711=462，M2=5711=385，M3=5611=330，M4=567=210，解同余式462M11(mod5)得M1=3385M21(mod6)得M2=1330M31(mod5)得M3=1210M41(mod5)得M4=1因此同余式组的解为x3462b1+1385b2+1330b3+1210b4(mod2310)。例2韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人。求兵数。解设兵数为x，则x1(mod5),x5(mod6),x4(mod7),x10(mod11)故解为x34621+13855+13304

13、+12101067312111(mod2310)。定理2同余式组xbi(modmi)，i=1,2,L,k有解的充分必要条件是bibj(mod(mi,mj)，ij=1,2,L,k。若上述条件成立，则同余式组对模m1,m2,L,mk有唯一解。- 6 - 第四章 同余式 例3解同余式组x8(mod15),x3(mod10),x1(mod8)。解因为83(mod(15,10),81(mod(15,8),31(mod(10,8)，所以同余式组有唯一解。先解同余式组x8(mod15),x3(mod10)。由x8(mod15)可知x=8+15y，代入x3(mod10)得代入得x23(mod30)。x23(m

14、od30),x1(mod8)，x113(mod120)。y1(mod2)，再解同余式组可得原同余式组的解是另解原同余式组可化为x8(mod5)x8(mod3)x3(mod5)，即x3(mod2)3x1(mod2)由孙子定理可解得x3(mod5)x2(mod3) x1(mod23)x113(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

15、(x)+r(x)，(r(x)p-1，f(x)r(x)(modp)，由费马定理可知，xZ，有xp-x0(modp)，于是因此，同余式(1)与r(x)0(modp)等价。定理2设kn，而xai(modp)，i=1,2,L,k是(1)的k个不同的解，则xZ，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)，所以r0(modp)，于是f(x)(x-a1)f1(x)(modp

16、)，令x=ai，i=2,3,L,k，则0(ai-a1)f1(ai)(modp)，又ai/a1(modp)，p为质数，故f1(ai)0(modp)，从而由归纳法可得结论。定理3(1)xZ，xp-1-1(x-1)(x-2)L(x-(p-1)(modp)；(2)(Wilson 定理)(p-1)!+10(modp)。证明(1)因为(i,p)=1，i=1,2,L,p-1，所以由欧拉定理可知1,2,L,p-1都是xp-1-10(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

17、(x-(p-1)(modp)。(2)在(1)中令x=0，则(-1)(-2)L(-(p-1)-1(modp)，当p=2时，结论显然成立；当p为奇质数时，(p-1)!+10(modp)。- 8 - 第四章 同余式 定理4同余式(1)的解数不超过它的次数。证明设(1)的解数超过n，则(1)至少有n+1个解，设为xai(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

18、,L,n，有ai=an+1(modp)，矛盾，因此，结论成立。定理5若np，则同余式(1)有n个解的充分必要条件是f(x)除xp-x所得余式的一切系数都是p的倍数。证明由多项式的带余除法可知xp-x=f(x)q(x)+r(x)，(r(x)n，若(1)有n个解，则由费马定理可知这n个解都是xp-x0(modp)的解，于是这n个解也是r(x)0(modp)的解，但(r(x)p，则可用xp-x去除f(x)，则可得到一个次数较低的与原同余式等价的同余式； (3)若f(x)关于模p有一个或几个因式，则也可将原同余式的次数降低； (4)若f(x)已知有一解或几解，则可析出因式将次数降低。 2、将模的完全剩

19、余系中的数逐一代入同余式，检验即可得解。 - 9 - 第四章 同余式 例解同余式f(x)=x7-2x6-7x5+x+20(mod5)。x7-2x6-2x5+x+20(mod5)，解化简系数，得用x5-x去除，得r(x)=x3-2x2-x+20(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表示

20、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个不同的解为xbiti(modmi)

21、，ti=1,2,L,Ti，i=1,2,L,k，则同余式组f(x)0(modmi)，i=1,2,L,k的解即为下列同余式组的解xb1t1(modm1),xb2t2(modm2),L,xbktk(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+90(mod35)。f(x)0(mod5)，f(x)0(mod7)等价，解原同余式与同余式组而

22、同余式同余式f(x)0(mod5)的解为x1,4(mod5)，f(x)0(mod7)的解为x3,5,6(mod7)，故原同余式有6个解，它们分别是下列同余式组的解：x1(mod5)x4(mod5)，x3,5,6(mod7)x3,5,6(mod7)由孙子定理可得6个解为：x6,19,24,26,31,34(mod35)。- 11 - 第四章 同余式 定理2设xx1(modp)，即x=x1+pt1，t1Z是f(x)0(modp)的一解，并且p/|f(x1)，则x=x1+pt1恰好给出了f(x)0(modpa)的一解(对模pa来说)：x=xa+pata，taZ，即xxa(modpa)，其中xax1(

23、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有唯一解：t1t1(modp)，即t1=t1+pt2，t2Z，代入x=x1+pt1得x=x1+p(t1+pt2)=x2+p2t2，t2Z，其中x2x1(modp)。假设结论对之情形成立，即x=x1+pt1恰好给出了f(x)0(modpa-1)的一解：x=xa-1+pa-1t

24、a-1，ta-1Z，xa-1x1(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-1x1(modp)，所以f(xa-1)f(x1)(modp)，从而p/|f(xa-1)，故上面同余式有唯一解：ta-1ta-1(modp)，即ta-1=ta-1+pta，taZ，代入x=xa-1+pa-1ta-1得f(x)0(modpa-1)的一解：x=xa-1+pa-1(ta-1+pta)=xa+pata，taZ，其中xax1(modp)。因此，结论普遍成立。- 1

25、2 - 第四章 同余式 例2解同余式f(x)=x4+7x+40(mod27)。解首先求得f(x)0(mod3)的解为x1(mod3)，并且f(1)/0(mod3)；将x=1+3t1代入f(x)0(mod9)得到f(1)+3t1f(1)0(mod9)，即3+6t10(mod9)，解得t11(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+180t20(mod27)，解得t22(mod3)，令t2=2+3t3，则x3=22+27t

26、3是f(x)0(mod27)的一个解，因此，原同余式的解为例3解同余式x22(mod27)。f(x)=x3-2x+60(mod53)。解首先求得f(x)0(mod5)有两个解：x1,2(mod5)。先讨论x11(mod5)，将x1=1+5t1代入f(x)0(mod52)得f(1)+5t1f(1)0(mod52)，即5+5t10(mod52)，解得t1-1(mod5)，令t1=-1+5t2，则x2=-4+25t2，将x2=-4+25t2代入f(x)0(mod53)得f(-4)+25t2f(-4)0(mod53)，即-50+2546t20(mod53)，x3=46+125t3，即x46(mod53)解得t22(mod5)，令t2=2+5t3，则是f(x)0(mod53)的一个解；再讨论x12(mod5)，将x1=2+5t1代入f(x)0(mod52)得f(2)+5t1f(2)0(mod52)，即10+50t10(mod52)，此同余式无解；x46(mod53)。因此，原同余式的解为解法总结：aka1a2mZ+，m=p1p2Lpk，要解同余式f(x)0(modm)，只需解 f(x)0(modpiai)，i=1,2,L,k，从而转化为解质数模的同余式。- 13 -