孙子定理和同余方程组市公开课一等奖省赛课获奖课件

孙子定理和同余方程组第1页

问题提出代数主要问题就是解方程隋朝之前有部《孙子算经》提出“物不知数”问题：今有物不知数，三三数之有二，五五数之有三，七七数之有二，问物有几何韩信点兵有兵一队，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵数处理：大衍求一术，鬼谷算天文、历法需要第2页孙子定理明朝程大位《算数统筹》

三人同行七十稀，五树梅花甘一枝，七子团圆整半月，除百零五便得知。

第3页孙子定理利用算式表示：２

７０＋３

２１＋２

１５＝２３３

再把２３３－１０５－１０５＝２３233+105n均是答案

３除余数５除余数７除余数７０１００２１０１０１５００１

３除余数５除余数７除余数７０

２２００２１

３０３０１５

２００２２３３２＋０＋０＝２０＋３＋０＝３２＋０＋０＝２三人同行七十稀五树梅花甘一枝七子团圆整半月除百零五便得知第4页孙子定理设m1,…,mk是k个两两互素正整数,若令

m=m1…mk,m=miMi,i=1,…,k,

则对任意整数b1,…,bk,同余方程组

有唯一解其中第5页孙子定理x≡462*3*1+385*5*1+330*4*1+210*10*1(mod2310)≡6731≡2111(mod2310)第6页同余方程组同余方程组有解充要条件是(m1,m2)|b1-b2.假如上述条件成立,则同余方程组模[m1,m2]有唯一解.证实设(m1,m2)=d,先证必要性.若x0为同余方程组解,则有x0≡b1(modd),x0≡b2(modd),两式相减得b1-b2≡0(modd),所以d|b1-b2.再证充分性.若d|b1-b2,则因x≡b1(modm1)解可写为x=b1+m1y,将其代入x≡b2(modm2)得m1y≡b2-b1(modm2).因为(m1,m2)=d,d|b2-b1,故上式有解,即原同余方程组有解.设原同余方程组有两个解分别为x1和x2,则x1

-

x2≡0(modm1), x1

-

x2≡0(modm2),于是有x1

-

x2≡0(mod[m1,m2]),即同余方程组模[m1,m2]有唯一解

第7页第8页同余方程组练习解方程组：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)即：3x≡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)第9页孙子定理应用第10页孙子定理应用求m≡51675(mod1081)m≡51675≡(46+5)22*30+15≡515≡5*257≡5*27≡20*32≡-4(mod23)m≡51675≡(47+4)46*14+31≡262≡216≡212≡18(mod47)m≡-4*47*1+18*23*(-2)≡-1063≡65(mod1081)第11页孙子定理孙子定理最大价值不在于直接解同余方程组而在于大模一个同余式化为小模、模互质同余方程组然后利用欧拉定理、费马小定理将式子化简经过解同余方程组来提升解原来同余式速度尤其是存在大指数情况更有效第12页法一：1012=127*8-4127=4*32-1所以（127，1012）=1，有解1=4*32-1271=(127*8-1012)*32-127=127*255-1012*32所以127*255≡1(mod1012)所以两边同乘以255255*127x≡255*833(mod1012)≡907(mod1012)练习解127x≡833(mod1012)第13页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)对于第一个：M1=11*23=253因为253≡1(mod4),M1’=1对于第二个：M2=4*23=92因为92≡4(mod11),M2’=3对于第三个：M3=4*11=44因为