孫子定理和同余方程組講解學習

1、孫子定理和同余方程組 問題的提出問題的提出代數(shù)的主要問題就是解方程隋朝之前有部孫子算經(jīng)提出“物不知數(shù)”問題：n今有物不知數(shù)，三三數(shù)之有二，五五數(shù)之有三，七七數(shù)之有二，問物有幾何韓信點兵n有兵一隊，若列成五行，末行一人，若列成六行，末行五人，列成七行，末行四人，列成十一行，末行十人，求兵數(shù)解決：大衍求一術(shù)，鬼谷算天文、歷法的需要孫子定理孫子定理x462*3*1+385*5*1+330*4*1+210*10*1(mod 2310) 6731 2111 (mod 2310)同余方程組同余方程組同余方程組 有解的充要條件是(m1,m2)|b1-b2. 如果上述條件成立, 則同余方程組模m1,m2有唯一

2、解.證明 設(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, 則x1 - x2 0 (mod m1), x1 - x2 0 (mod m2),于是有x1 - x2 0 (mod

3、 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(mod 3)所以只有3個：3x2(mod 5)，x1(mod 2)和7x5(mod 9)解：x4*2*2*9+1*1*

4、5*9+2*1*5*220929(mod 90)系數(shù)都化為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孫子定理的最大價值不在于直接解同余方程組n而在于大模的一個同余式化為小模的、?；ベ|(zhì)的同余方程組n然后利用歐拉定理、費馬小定理將

5、式子化簡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) 練習練習解 127x833(mod 1012)1012=4*11*23，所以化為方程組127x833(mod 4) 化簡為：x-1(mod 4) 127x833(mod 11) 化簡為：6x-

6、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網(wǎng)絡熱身賽網(wǎng)絡熱身賽青蛙的約會 兩只青蛙在網(wǎng)上相識了，覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面