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

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

2、 除余數(shù)除余數(shù)除余數(shù)三人同行七十稀三人同行七十稀五樹(shù)梅花甘一枝五樹(shù)梅花甘一枝七子團(tuán)圓整半月七子團(tuán)圓整半月除百零五便得知除百零五便得知孫子定理孫子定理設(shè)m1,mk是k個(gè)兩兩互素的正整數(shù), 若令 m = m1mk, m = miMi, i = 1,k, 則對(duì)任意的整數(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)的解可寫(xiě)為x=b1+m1y,將其代入x b2 (mod m2)得m1yb2-b1 (mod m2).因?yàn)?m1,m2) = d, d|b2-b1, 故上式有解, 即原同余方程組有解.設(shè)原同余方程組有兩個(gè)解分別為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)對(duì)于7x5(mod 9)可以推出7x5(mod 3)即x2(mo

5、d 3)所以只有3個(gè)：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、大價(jià)值不在于直接解同余方程組n而在于大模的一個(gè)同余式化為小模的、?；ベ|(zhì)的同余方程組n然后利用歐拉定理、費(fèi)馬小定理將式子化簡(jiǎn)n通過(guò)解同余方程組來(lái)提高解原來(lái)同余式的速度特別是存在大指數(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) 化簡(jiǎn)為：x-1(mod 4) 127x833(mod 11) 化簡(jiǎn)為：6x-3(mod 11)= x5(mod 11)127x833(mod 23) 化簡(jiǎn)為：12x5(mod 23)= x10(mod 23)對(duì)于第一個(gè)：M1=11*23=253 因?yàn)?531(mod 4),M1=1對(duì)于第二個(gè)：M2=4*23=92 因?yàn)?24(mod 11),M2=3對(duì)于第三個(gè)：M3=4*11=44 因?yàn)?4-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ò)熱身賽青蛙的約會(huì) 兩只青蛙在網(wǎng)上相識(shí)了，覺(jué)得很有必要見(jiàn)一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂(lè)觀的，它們覺(jué)得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂(lè)觀的青蛙，你被要求寫(xiě)一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。 青蛙A和青蛙B，規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長(zhǎng)度1米，青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，一次能跳m米;青