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

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

2、 除余数除余数除余数三人同行七十稀三人同行七十稀五树梅花甘一枝五树梅花甘一枝七子团圆整半月七子团圆整半月除百零五便得知除百零五便得知孙子定理孙子定理设m1,mk是k个两两互素的正整数, 若令 m = m1mk, m = miMi, i = 1,k, 则对任意的整数b1,bk, 同余方程组 有唯一解 其中)(mod )(mod 11kkmbxmbx)(mod 222111mbMMbMMbMMxkkk1 (mod) 1,2,iiiM Mmik孙子定理孙子定理x462*3*1+385*5*1+330*4*1+210*10*1(mod 2310) 6731 2111 (mod 2310)同余方程组同余

3、方程组同余方程组 有解的充要条件是(m1,m2)|b1-b2. 如果上述条件成立, 则同余方程组模m1,m2有唯一解.证明 设(m1,m2) = d, 先证必要性. 若x0为同余方程组的解, 则有x0 b1 (mod d), x0 b2 (mod d),两式相减得b1-b20(mod d), 因此d|b1-b2.再证充分性. 若d|b1-b2, 则因xb1 (mod m1)的解可写为x=b1+m1y,将其代入x b2 (mod m2)得m1yb2-b1 (mod m2).因为(m1,m2) = d, d|b2-b1, 故上式有解, 即原同余方程组有解.设原同余方程组有两个解分别为x1和x2,

4、则x1 - x2 0 (mod m1), x1 - x2 0 (mod m2),于是有x1 - x2 0 (mod m1,m2), 即同余方程组模m1,m2有唯一解 )(mod )(mod 2211mbxmbx同余方程组同余方程组练习解方程组：7x5(mod 18)； 13x2(mod 15)首先7x5(mod 18)化为：7x5(mod 2)和7x5(mod 9)即： x1(mod 2)和7x5(mod 9)13x2(mod 15)化为:13x2(mod 5)和13x2(mod 3)即： 3x2(mod 5)和x2(mod 3)对于7x5(mod 9)可以推出7x5(mod 3)即x2(mo

5、d 3)所以只有3个：3x2(mod 5)，x1(mod 2)和7x5(mod 9)解：x4*2*2*9+1*1*5*9+2*1*5*220929(mod 90)系数都化为1: x4(mod 5)，x1(mod 2)和 x2(mod 9)孙子定理孙子定理的应用的应用孙子定理的应用孙子定理的应用求m51675(mod 1081) 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(mod 1081)孙子定理孙子定理n孙子定理的最

6、大价值不在于直接解同余方程组n而在于大模的一个同余式化为小模的、模互质的同余方程组n然后利用欧拉定理、费马小定理将式子化简n通过解同余方程组来提高解原来同余式的速度特别是存在大指数的情况更有效法一：1012=127*8-4 127=4*32-1所以 （127，1012）=1，有解1=4*32-127 1=(127*8-1012)*32-127=127*255-1012*32所以127*255 1(mod 1012) 所以两边同乘以255255*127x 255*833(mod 1012) 907(mod 1012) 练习练习解 127x833(mod 1012)1012=4*11*23，所以化

7、为方程组127x833(mod 4) 化简为：x-1(mod 4) 127x833(mod 11) 化简为：6x-3(mod 11)= x5(mod 11)127x833(mod 23) 化简为：12x5(mod 23)= x10(mod 23)对于第一个：M1=11*23=253 因为2531(mod 4),M1=1对于第二个：M2=4*23=92 因为924(mod 11),M2=3对于第三个：M3=4*11=44 因为44-2(mod 23)，M3=11求和：x253*(-1)*1+92*5*3+44*10*11 -253+1380+48405967907 (mod 1012)练习练习解 127x833(mod 1012)北大北大ACM网络热身赛网络热身赛青蛙的约会 两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 青蛙A和青蛙B，规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，青蛙A的出发点坐标是x，一次能跳m米;青