剩余定理公式.ppt

中国剩余定理,今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？解答：三三数之有二对应140，五五数之有三对应63，七七数之有二对应30，这些数相加得到233，再减210，即得数23。同余方程式：xmod3=2xmod5=3xmod7=22572=1401373=631352=302357=210,定理1设m1,m2,mk是两两互素的正整数，则对任意b1,b2,bk，同余方程组xmodm1=b1modm1,xmodm2=b2modm2,xmodmk=bkmodmk,其解为：x=(M1M1b1+M2M2b2+MkMkbk)modmm=m1m2mk,复习Mi=m/miMiMimodmi=1显然(Mi,mi)=1即Mi是Mi的逆元Mi(mi)-1modmi或者可用辗转相除法求Mi.,定理4:mZ+,aZ,a是模m简化剩余的充要条件a是模m的可逆元。必要性:a简化剩余则a可逆a简化剩余(a,m)=1axmodm=1有惟一解a,即aamodm=1a是可逆元。充分性:a可逆则a是简化剩余a可逆存在a，使得aamodm=1则方程axmodm=1有解，根据定理1的必要可知(a,m)|b即(a,m)|1故(a,m)=1,例:xmod3=2xmod5=3xmod7=2m1=3m2=5m3=7b1=2b2=3b3=2m=m1m2m3=357M1=m/m1=57M1=Mi(mi)-1modmi=2M2=m/m2=37M2=Mi(mi)-1modmi=1M3=m/m3=35M3=Mi(mi)-1modmi=1x=(M1M1b1+M2M2b2+MkMkbk)modm=(2*5*7*2+1*3*7*3+1*3*5*2)mod105=(140+63+30)mod105=233mod105=23,例2xmod5=b1xmod6=b2xmod7=b3xmod11=b4m1=5m2=6m3=7m4=11m=m1m2m3m4=56711M1=m/m1=6711=462M1=Mi(mi)-1modmi=3M2=m/m2=5711=385M2=Mi(mi)-1modmi=1M3=m/m3=5611=330M3=Mi(mi)-1modmi=1M4=m/m4=567=210M4=Mi(mi)-1modmi=1x=(M1M1b1+M2M2b2+M3M3b3+M4M4b4)modm=(462*3*b1+385*1*b2+330*1*b3+210*1*b4)modm,xmod5=b1xmod6=b2xmod7=b3xmod11=b4m1=5m2=6m3=7m4=11M1=m/m1=6711=462M1M1modm1=1M2=m/m2=5711=385M2M2modm2=1M3=m/m3=5611=330M3M3modm3=1M4=m/m4=567=210M4M4modm4=1M1M1modm1=1M1M1=km1+1M1M1+km1=1(M1,m1)=1最大公约数为1，M1,k为组合系数利用辗转相除法求最大约数,然后求组合系数。462=92*5+25=2*2+11=5-2*21=5-(462-92*5)*2462*(-2)+5*(1+2*92)=1462*(-5+3)+5*(1+2*92)=1462*3+5*(1+2*92-462)=1M1=3,例3xmod5=1xmod6=5xmod7=4xmod11=10 x=(M1M1b1+M2M2b2+M3M3b3+M4M4b4)modm=(462*3*1+385*1*5+330*1*4+210*1*10)modm=6731mod2310=2111mod2310=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故Mixmodmi=1有解MiMiMimodmi=1从(1)可知当ji时mj|Mi则Mimodmj=0(M1M1a1+M2M2a2+MjMjaj+.+MkMkak)modmj=MjMjajmodmi=ajmodmi.xmodmi=aimodmi即满足方程。,证明:惟一性，同一等价类的数看成一个根若x1,x2均是方程的根,x1modmi=aimodmi=x2modmim=m1m2.mk又m1,m2,mk两两互素则x1modm=x2modmx1,x2同属一个同余类，即是同一解。,21000000mod77=?,解二77=7*11x=21000000,xmod77=?xmod7=b1xmod11=b2this!1b1,b2可求出，问xmod77=?2(7)261mod7EulerTh.1000000=166666*6+4X=21000000=2166666*6+4=(26)166666242mod72(11)2101mod11EulerTh.1000000=100000*10X=21000000=2100000*10=(210)1000001mod11xmod7=2xmod11=1求xmod77=?m1=7m2=11m=m1*m2=77M1=m/m1=11M2=m/m2=7,解二77=7*11x=21000000,xmod77=?xmod7=2xmod11=1求xmod77=?m1=7m2=11m=m1*m2=77M1=m/m1=11M2=m/m2=7M1M1modm1=1M1的逆元M2M2modm2=