例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=m1m2„mk M1 M2 „ Mk M1’ M2’ „ Mk’ 各 总 M1M1’b1 M2M2’b2 „ MkMk’bk 答数 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。