孫子定理和同余方程組-課件PPT

1、孫子定理和同余方程組孫子定理和同余方程組 問題的提出問題的提出代數(shù)的主要問題就是解方程隋朝之前有部孫子算經(jīng)提出“物不知數(shù)”問題：n今有物不知數(shù)，三三數(shù)之有二，五五數(shù)之有三，七七數(shù)之有二，問物有幾何韓信點兵n有兵一隊，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵數(shù)解決：大衍求一術(shù)，鬼谷算天文、歷法的需要孫子定理孫子定理明朝程大位算數(shù)統(tǒng)籌 三人同行七十稀，三人同行七十稀， 五樹梅花甘一枝，五樹梅花甘一枝， 七子團圓整半月，七子團圓整半月， 除百零五便得知。除百零五便得知。 孫子定理孫子定理利用算式表示： 再把233+105n均是答案 除余數(shù)除余數(shù)除余數(shù)

2、 除余數(shù)除余數(shù)除余數(shù)三人同行七十稀三人同行七十稀五樹梅花甘一枝五樹梅花甘一枝七子團圓整半月七子團圓整半月除百零五便得知除百零五便得知孫子定理孫子定理設(shè)m1,mk是k個兩兩互素的正整數(shù), 若令 m = m1mk, m = miMi, i = 1,k, 則對任意的整數(shù)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有唯一解.證明 設(shè)(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, 故上式有解, 即原同余方程組有解.設(shè)原同余方程組有兩個解分別為x1和x2,

4、則x1 - x2 0 (mod m1), x1 - x2 0 (mod m2),于是有x1 - x2 0 (mod m1,m2), 即同余方程組模m1,m2有唯一解 )(mod )(mod 2211mbxmbx同余方程組同余方程組練習(xí)解方程組：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)系數(shù)都化為1: x4(mod 5)，x1(mod 2)和 x2(mod 9)孫子定理孫子定理的應(yīng)用的應(yīng)用孫子定理的應(yīng)用孫子定理的應(yīng)用求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而在于大模的一個同余式化為小模的、?；ベ|(zhì)的同余方程組n然后利用歐拉定理、費馬小定理將式子化簡n通過解同余方程組來提高解原來同余式的速度特別是存在大指數(shù)的情況更有效法一：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) 練習(xí)練習(xí)解 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)練習(xí)練習(xí)解 127x833(mod 1012)北大北大ACM網(wǎng)絡(luò)熱身賽網(wǎng)絡(luò)熱身賽青蛙的約會 兩只青蛙在網(wǎng)上相識了，覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。 青蛙A和青蛙B，規(guī)定緯度線上東經(jīng)0度處為原點，由東往西為正方向，單位長度1米，青蛙A的出發(fā)點坐標(biāo)是x，一次能跳m米;青