孙子定理和同余方程组.ppt

《孙子定理和同余方程组.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、孙子定理和同余方程组问题的提出代数的主要问题就是解方程隋朝之前有部《孙子算经》提出“物不知数”问题：今有物不知数，三三数之有二，五五数之有三，七七数之有二，问物有几何韩信点兵有兵一队，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵数解决：大衍求一术，鬼谷算天文、历法的需要孙子定理明朝程大位《算数统筹》三人同行七十稀，五树梅花甘一枝，七子团圆整半月，除百零五便得知。孙子定理利用算式表示：２７０＋３２１＋２１５＝２３３再把２３３－１０５－１０５＝２３

2、233+105n均是答案３除余数５除余数７除余数７０１００２１０１０１５００１３除余数５除余数７除余数７０２２００２１３０３０１５２００２２３３２＋０＋０＝２０＋３＋０＝３２＋０＋０＝２三人同行七十稀五树梅花甘一枝七子团圆整半月除百零五便得知孙子定理设m1,…,mk是k个两两互素的正整数,若令m=m1…mk,m=miMi,i=1,…,k,则对任意的整数b1,…,bk,同余方程组有唯一解其中孙子定理x≡462*3*1+385*5*1+330*4*1+210*10*1(mod2310)≡673

3、1≡2111(mod2310)同余方程组同余方程组有解的充要条件是(m1,m2)

4、b1-b2.如果上述条件成立,则同余方程组模[m1,m2]有唯一解.证明设(m1,m2)=d,先证必要性.若x0为同余方程组的解,则有x0≡b1(modd),x0≡b2(modd),两式相减得b1-b2≡0(modd),因此d

5、b1-b2.再证充分性.若d

6、b1-b2,则因x≡b1(modm1)的解可写为x=b1+m1y,将其代入x≡b2(modm2)得m1y≡b2-b1(modm2).因为(m1,m2)=d,d

7、

8、b2-b1,故上式有解,即原同余方程组有解.设原同余方程组有两个解分别为x1和x2,则x1-x2≡0(modm1),x1-x2≡0(modm2),于是有x1-x2≡0(mod[m1,m2]),即同余方程组模[m1,m2]有唯一解同余方程组练习解方程组：7x≡5(mod18)；13x≡2(mod15)首先7x≡5(mod18)化为：7x≡5(mod2)和7x≡5(mod9)即：x≡1(mod2)和7x≡5(mod9)13x≡2(mod15)化为:13x≡2(mod5)和13x≡2(mod3)即：3

9、x≡2(mod5)和x≡2(mod3)对于7x≡5(mod9)可以推出7x≡5(mod3)即x≡2(mod3)所以只有3个：3x≡2(mod5)，x≡1(mod2)和7x≡5(mod9)解：x≡4*2*2*9+1*1*5*9+2*1*5*2≡209≡29(mod90)系数都化为1:x≡4(mod5)，x≡1(mod2)和x≡2(mod9)孙子定理的应用孙子定理的应用求m≡51675(mod1081)m≡51675≡(46+5)22*30+15≡515≡5*257≡5*27≡20*32≡-4(mo

10、d23)m≡51675≡(47+4)46*14+31≡262≡216≡212≡18(mod47)m≡-4*47*1+18*23*(-2)≡-1063≡65(mod1081)孙子定理孙子定理的最大价值不在于直接解同余方程组而在于大模的一个同余式化为小模的、模互质的同余方程组然后利用欧拉定理、费马小定理将式子化简通过解同余方程组来提高解原来同余式的速度特别是存在大指数的情况更有效法一：1012=127*8-4127=4*32-1所以（127，1012）=1，有解1=4*32-1271=(127*8-

11、1012)*32-127=127*255-1012*32所以127*255≡1(mod1012)所以两边同乘以255255*127x≡255*833(mod1012)≡907(mod1012)练习解127x≡833(mod1012)1012=4*11*23，所以化为方程组127x≡833(mod4)化简为：x≡-1(mod4)127x≡833(mod11)化简为：6x≡-3(mod11)=>x≡5(mod11)127x≡833(mod23)化简为：12x≡5(mod23)=>x≡10(mod23

12、)对于第一个：M1=11*23=253因为253≡1(mod4),M1’=1对于第二个：M2=4*23=92因为92≡4(mod11),M2’=3对于第三个：M3=4*11=44因为44≡-2(mod23)，M3’=11求和：x≡253*(-1)*1+92*5*3+44*10*11≡-253+1380+4840≡5967≡907(mod1012)练习解127x≡833(mod1012)北大ACM网络热身赛青蛙的约会两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，