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

2、 若令 m = m1mk, m = miMi, i = 1,k, 則對(duì)任意的整數(shù)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有唯一解. 證明 設(shè)(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). 因?yàn)?m1,m2) = d, d|b2-b1, 故上式有解, 即原同余方程組有解. 設(shè)原同余方程組有兩個(gè)解分別為x1和x2, 則 x1 - x2 0 (mod m1),x1 - x2 0 (mod m2), 于是有x1 - x2 0 (mod m1,m2), 即同余方程組模m1,m2有唯一解,同余方程組,練習(xí)解方程組：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),對(duì)于7x5(mod 9)可以推出7x5(mod 3)即x2(mod 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)用,求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),孫子定理,孫子定理的最大價(jià)值不在于直接解同余方程組 而在于大模的一個(gè)同余式化為小模的、?；ベ|(zhì)的同余方程組 然后利用歐拉定理、費(fèi)馬小定理將式子化簡(jiǎ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*3

6、2 所以127*255 1(mod 1012) 所以兩邊同乘以255 255*127x 255*833(mod 1012) 907(mod 1012),練習(xí),解 127x833(mod 1012),1012=4*11*23，所以化為方程組 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)?2

7、4(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í),解 127x833(mod 1012),北大ACM網(wǎng)絡(luò)熱身賽,青蛙的約會(huì) 兩只青蛙在網(wǎng)上相識(shí)了，覺(jué)得很有必要見(jiàn)一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂(lè)觀的，它們覺(jué)得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂(lè)觀的青蛙，你被要求寫一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)