中国的剩余定理.ppt

中国剩余定理; 今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？ 解答：三三数之有二对应140，五五数之有三对应63，七七数之有二对应30，这些数相加得到233，再减210，即得数23。 同余方程式： x mod 3=2 x mod 5=3 x mod 7=2 2?5?7?2=140 1?3?7?3=63 1?3?5?2=30 2 ?3?5?7=210;定理1 设m1,m2,…mk是两两互素的正整数，则对任意b1,b2,…,bk，同余方程组 x mod m1=b1 mod m1, x mod m2=b2 mod m2, … x mod mk=bk mod mk, 其解为： x=(M1’M1b1+M2’M2b2+…+M’kMkbk )mod m m=m1m2…mk, 复习 Mi=m/mi MiMi’ mod mi=1 显然(Mi,mi)=1 即Mi’是Mi的逆元Mi?(mi)-1mod mi或者可用辗转相除法求Mi’.;定理4: m?Z+, a?Z,a是模m简化剩余的充要条件a是模m的可逆元。 必要性:a简化剩余则a可逆 a简化剩余?(a,m)=1?ax mod m=1有惟一解a’,即aa’ mod m=1?a是可逆元。 充分性:a可逆则a是简化剩余 a可逆?存在a’，使得aa’ mod m=1 ? 则方程ax mod m=1有解，根据定理1的必要可知(a,m)|b即 (a,m)|1 故 (a,m)=1; 例: x mod 3=2 x mod 5=3 x mod 7=2 m1=3 m2=5 m3=7 b1=2 b2=3 b3=2 m=m1?m2?m3=3?5?7 M1=m/m1=5?7 M1’=Mi?(mi)-1mod mi=2 M2=m/m2=3?7 M2’=Mi?(mi)-1mod mi=1 M3=m/m3=3?5 M3’=Mi?(mi)-1mod mi=1 x=(M1’M1b1+M2’M2b2+…+M’kMkbk )mod m =(2*5*7*2+1*3*7*3+1*3*5*2)mod 105 =(140+63+30) mod 105=233 mod 105=23; 例2 x mod 5=b1 x mod 6=b2 x mod 7=b3 x mod 11=b4 m1=5 m2=6 m3=7 m4=11 m=m1?m2?m3?m4=5?6?7?11 M1=m/m1= 6?7?11=462 M1’=Mi?(mi)-1mod mi=3 M2=m/m2=5?7?11=385 M2’=Mi?(mi)-1mod mi=1 M3=m/m3=5?6?11=330 M3’=Mi?(mi)-1mod mi=1 M4=m/m4=5?6?7=210 M4’=Mi?(mi)-1mod mi=1 x=(M1’M1b1+M2’M2b2+M’3M3b3 +M’4M4b4)mod m =(462*3*b1+385*1*b2+330*1*b3+210*1*b4)mod m;x mod 5=b1 x mod 6=b2 x mod 7=b3 x mod 11=b4 m1=5 m2=6 m3=7 m4=11 M1=m/m1= 6?7?11=462 M1’M1mod m1=1 M2=m/m2=5?7?11=385 M2’M2mod m2=1 M3=m/m3=5?6?11=330 M3’M3mod m3=1 M4=m/m4=5?6?7=210 M4’M4mod m4=1 M1’M1mod m1=1?M1’M1=km1+1?M1’M1+k’m1=1 ?(M1,m1)=1最大公约数为1，M1’,k’为组合系数 ?利用辗转相除法求最大约数,然后求组合系数。 462=92*5+2 ? 5=2*2+1 ? 1=5-2*2 ? 1=5-(462-92*5)*2 ?462*(-2)+5*(1+2*92)=1 ?462*(-5+3)+ 5*(1+2*92)=1 ?462*3+5*(1+2*92-462)=1?M1’=3; 例3 x mod 5=1 x mod 6=5 x mod 7=4 x mod 11=10 x=(M1’M1b1+M2’M2b2+M’3M3b3 +M’4M4b4)mod m =(462*3*1+385*1*5+330*1*4+210*1*10)mod m =6731 mod 2310=2111 mod 2310=2111 ;证明:验证x满足方程 (mi,m1)=1,(mi,m2)=1,... (mi,mi-1)=1 (mi,mi+1)=1…(mi,m