《剩余定理公式》PPT课件.ppt

《《剩余定理公式》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《剩余定理公式》PPT课件.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、中国剩余定理中国剩余定理今有物不知其数，三三数之有二，五五今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？数之有三，七七数之有二，问物有多少？解答解答：三三数之有二对应：三三数之有二对应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是两两互素的正整是两两

2、互素的正整数，则对任意数，则对任意b1,b2,bk，同余方程组，同余方程组x mod m1=b1 mod m1,x mod m2=b2 mod m2,x mod mk=bk mod mk,其解为：其解为：x=(M1M1b1+M2M2b2+MkMkbk)mod mm=m1m2mk,复习复习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简化剩余则简化

3、剩余则a可逆可逆 a简化剩余简化剩余(a,m)=1ax mod m=1有有惟一解惟一解a,即即aa mod m=1a是可逆元。是可逆元。充分性充分性: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=2m=m1 m2 m3=3 5 7M1=m/m1=5 7 M1=Mi(mi)-1mod mi=2M2

4、=m/m2=3 7 M2=Mi(mi)-1mod mi=1M3=m/m3=3 5 M3=Mi(mi)-1mod mi=1x=(M1M1b1+M2M2b2+MkMkbk)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 11M1=m/m1=6 7 11=462 M1=Mi(mi)-1mod mi=3M2=m/m2=5 7 1

5、1=385 M2=Mi(mi)-1mod mi=1M3=m/m3=5 6 11=330 M3=Mi(mi)-1mod mi=1M4=m/m4=5 6 7=210 M4=Mi(mi)-1mod mi=1x=(Mx=(M1 1MM1 1b b1 1+M+M2 2MM2 2b b2 2+M+M3 3MM3 3b b3 3+M+M4 4MM4 4b b4 4)mod m)mod m=(462*3*b1+385*1*b2+330*1*b3+210*1*b4=(462*3*b1+385*1*b2+330*1*b3+210*1*b4)mod m)mod mx mod 5=b1 x mod 6=b2 x mo

6、d 7=b3x mod 5=b1 x mod 6=b2 x mod 7=b3x mod 11=b4x mod 11=b4 m m1 1=5 m=5 m2 2=6 m=6 m3 3=7 m=7 m4 4=11=11MM1 1=m/m=m/m1 1=6=6 7 7 11=462 M11=462 M1 1MM1 1mod mmod m1 1=1=1MM2 2=m/m=m/m2 2=5=5 7 7 11=385 M11=385 M2 2MM2 2mod mmod m2 2=1=1MM3 3=m/m=m/m3 3=5=5 6 6 11=330 M11=330 M3 3MM3 3mod mmod m3 3

7、=1=1MM4 4=m/m=m/m4 4=5=5 6 6 7=210 M7=210 M4 4MM4 4mod mmod m4 4=1=1MM1 1MM1 1mod mmod m1 1=1=1MM1 1MM1 1=km=km1 1+1+1MM1 1MM1 1+km+km1 1=1=1(M(M1 1,m,m1 1)=1)=1最大公约数为最大公约数为最大公约数为最大公约数为1 1，MM1 1,k,k为组合系数为组合系数为组合系数为组合系数利用辗转相除法求最大约数利用辗转相除法求最大约数利用辗转相除法求最大约数利用辗转相除法求最大约数,然后求组合系数。然后求组合系数。然后求组合系数。然后求组合系数。4

8、62=92*5+2 462=92*5+2 5=2*2+1 5=2*2+1 1=5-2*2 1=5-2*2 1=5-(462-92*5)*2 1=5-(462-92*5)*2 462*(-2)+5*(1+2*92)=1462*(-2)+5*(1+2*92)=1462*(-5+3)+5*(1+2*92)=1462*(-5+3)+5*(1+2*92)=1462*3+5*(1+2*92-462)=1462*3+5*(1+2*92-462)=1MM1 1=3=3 例例3 x mod 5=1 x mod 6=5 x mod 7=4 x mod 11=10 x=(Mx=(M1 1MM1 1b b1 1+M+

9、M2 2MM2 2b b2 2+M+M3 3MM3 3b b3 3+M+M4 4MM4 4b b4 4)mod m)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,mk)=1 (mi,m1m2.mi-1mi+1mk)=1.(1)(mi,Mi)=1 故故 Mix mod mi=1 有解有解MiMiMi mod mi=1 从从(1)可知当可知当j i时时 mj|

10、Mi则则 Mi mod mj=0(M1M1a1+M2M2a2+MjMjaj+.+MkMkak)mod mj=MjMjajmod mi=ajmod mi.x mod mi=ai mod mi 即满足方程。即满足方程。证明证明:惟一性，同一等价类的数看成一个根惟一性，同一等价类的数看成一个根 若若x1,x2均是方程的根均是方程的根,x1 mod mi=ai mod mi=x2 mod mi m=m1m2.mk 又又m1,m2,mk两两互素两两互素 则则 x1mod m=x2 mod m x1,x2同属一个同余类，即是同一解。同属一个同余类，即是同一解。21000000mod 77=?解二解二77=

11、7*11 x=21000000,x mod 77=?x mod 7=b1 x mod 11=b2 this!1b1,b2可求出，问可求出，问 x mod 77=?2(7)26 1 mod 7 Euler Th.1000000=166666*6+4X=21000000=2166666*6+4=(26)16666624 2 mod 7 2(11)210 1 mod 11 Euler Th.1000000=100000*10X=21000000=2100000*10=(210)100000 1 mod 11 x mod 7=2 x mod 11=1 求求x mod 77=?m1=7 m2=11 m=

12、m1*m2=77 M1=m/m1=11 M2=m/m2=7 解二解二77=7*11 x=21000000,x mod 77=?x mod 7=2x mod 11=1 求求x mod 77=?m1=7 m2=11 m=m1*m2=77 M1=m/m1=11 M2=m/m2=7 M1M1 mod m1=1 M1的逆元的逆元 M2M2 mod m2=1 M2的逆元的逆元11M1 mod 7=1 M1=2=11=11 (7)-1(7)-1mod 7=11mod 7=115 5 mod7 mod7 7M2 mod 11=1 M2=8=7=7 (11)-1(11)-1mod 11=7mod 11=79 9 mod11mod11 x=(M1M1b1+M2M2b2)mod m=(11*2*2+7*8*1)mod m=23