好文档就是一把金锄头!
欢迎来到金锄头文库![会员中心]
电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

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

18页
  • 卖家[上传人]:ni****g
  • 文档编号:460024272
  • 上传时间:2022-09-02
  • 文档格式:DOCX
  • 文档大小:42.74KB
  • / 18 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 初等数论 第四章 同余式第四章 同余式 第四章 同余式 §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|b2)因为不定方程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

      例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。

      点击阅读更多内容
      关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
      手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
      ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.