孙子定理和同余方程组ppt课件

孙子定理和同余方程组,问题的提出,代数的主要问题就是解方程隋朝之前有部孙子算经提出“物不知数”问题：今有物不知数，三三数之有二，五五数之有三，七七数之有二，问物有几何韩信点兵有兵一队，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵数解决：大衍求一术，鬼谷算天文、历法的需要,孙子定理,明朝程大位算数统筹三人同行七十稀，五树梅花甘一枝，七子团圆整半月，除百零五便得知。,孙子定理,利用算式表示：再把233+105n均是答案,三人同行七十稀五树梅花甘一枝七子团圆整半月除百零五便得知,孙子定理,设m1,mk是k个两两互素的正整数,若令m=m1mk,m=miMi,i=1,k,则对任意的整数b1,bk,同余方程组有唯一解其中,孙子定理,x462*3*1+385*5*1+330*4*1+210*10*1(mod2310)67312111(mod2310),同余方程组,同余方程组有解的充要条件是(m1,m2)|b1-b2.如果上述条件成立,则同余方程组模m1,m2有唯一解.证明设(m1,m2)=d,先证必要性.若x0为同余方程组的解,则有x0b1(modd),x0b2(modd),两式相减得b1-b20(modd),因此d|b1-b2.再证充分性.若d|b1-b2,则因xb1(modm1)的解可写为x=b1+m1y,将其代入xb2(modm2)得m1yb2-b1(modm2).因为(m1,m2)=d,d|b2-b1,故上式有解,即原同余方程组有解.设原同余方程组有两个解分别为x1和x2,则x1-x20(modm1),x1-x20(modm2),于是有x1-x20(modm1,m2),即同余方程组模m1,m2有唯一解,同余方程组,练习解方程组：7x5(mod18)；13x2(mod15),首先7x5(mod18)化为：7x5(mod2)和7x5(mod9)即：x1(mod2)和7x5(mod9)13x2(mod15)化为:13x2(mod5)和13x2(mod3)即：3x2(mod5)和x2(mod3),对于7x5(mod9)可以推出7x5(mod3)即x2(mod3)所以只有3个：3x2(mod5)，x1(mod2)和7x5(mod9),解：x4*2*2*9+1*1*5*9+2*1*5*220929(mod90),系数都化为1:x4(mod5)，x1(mod2)和x2(mod9),孙子定理的应用,孙子定理的应用,求m51675(mod1081)m51675(46+5)22*30+155155*2575*2720*32-4(mod23)m51675(47+4)46*14+3126221621218(mod47)m-4*47*1+18*23*(-2)-106365(mod1081),孙子定理,孙子定理的最大价值不在于直接解同余方程组而在于大模的一个同余式化为小模的、模互质的同余方程组然后利用欧拉定理、费马小定理将式子化简通过解同余方程组来提高解原来同余式的速度特别是存在大指数的情况更有效,法一：1012=127*8-4127=4*32-1所以（127，1012）=1，有解1=4*32-1271=(127*8-1012)*32-127=127*255-1012*32所以127*2551(mod1012)所以两边同乘以255255*127x255*833(mod1012)907(mod1012),练习,解127x833(mod1012),1012=4*11*23，所以化为方程组127x833(mod4)化简为：x-1(mod4)127x833(mod11)化简为：6x-3(mod11)=x5(mod11)127x833(mod23)化简为：12x5(mod23)=x10(mod23)对于第一个：M1=11*23=253因为2531(mod4),M1=1对于第二个：M2=4*23=92因为924(mod11),M2=3对于第三个：M3=4*11=44因为44-2(mod23)，M3=11求和：x253*(-1)*1+92*5*3+44*10*11-253+1380+48405967907(mod1012),练习,解127x833(mod1012),北大ACM网络热身赛,青蛙的约会两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。