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

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

2、 若令 m = m1mk, m = miMi, i = 1,k, 则对任意的整数b1,bk, 同余方程组 有唯一解 其中,孙子定理,x462*3*1+385*5*1+330*4*1+210*10*1(mod 2310) 6731 2111 (mod 2310),同余方程组,同余方程组 有解的充要条件是(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. 再证充分性.

3、若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, 则 x1 - x2 0 (mod m1),x1 - x2 0 (mod m2), 于是有x1 - x2 0 (mod m1,m2), 即同余方程组模m1,m2有唯一解,同余方程组,练习解方程组：7x5(mod 18)； 13x2(mod 15),首先7x5(mod 18)化为：7x5(mod 2)和7x5(mod 9) 即

4、： 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(mod 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*

5、2575*2720*32-4(mod23) m51675(47+4)46*14+3126221621218(mod47) m-4*47*1+18*23*(-2)-106365(mod 1081),孙子定理,孙子定理的最大价值不在于直接解同余方程组 而在于大模的一个同余式化为小模的、模互质的同余方程组 然后利用欧拉定理、费马小定理将式子化简 通过解同余方程组来提高解原来同余式的速度 特别是存在大指数的情况更有效,法一：1012=127*8-4 127=4*32-1 所以 （127，1012）=1，有解 1=4*32-127 1=(127*8-1012)*32-127=127*255-1012*3

6、2 所以127*255 1(mod 1012) 所以两边同乘以255 255*127x 255*833(mod 1012) 907(mod 1012),练习,解 127x833(mod 1012),1012=4*11*23，所以化为方程组 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 因为92

7、4(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网络热身赛,青蛙的约会 两只青蛙在网上相识了，觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会