剩余定理公式

《剩余定理公式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国剩余定理今有物不知其数，三三数之有二，五五数之有三，七七数之有二，问物有多少？解答：三三数之有二对应140，五五数之有三对应63，七七数之有二对应30，这些数相加得到233，再减210，即得数23。同余方程式：xmod3=2xmod5=3xmod7=22572=1401373=631352=302357=210定理1设m1,m2,…mk是两两互素的正整数，则对任意b1,b2,…,bk，同余方程组xmodm1=b1modm1,xmodm2=b2modm2,…xmodmk=bkmodmk,其解为：x=(M1’M1b1+M2’M2b2+…+M’kMkb

2、k)modmm=m1m2…mk,复习Mi=m/miMiMi’modmi=1显然(Mi,mi)=1即Mi’是Mi的逆元Mi(mi)-1modmi或者可用辗转相除法求Mi’.定理4:mZ+,aZ,a是模m简化剩余的充要条件a是模m的可逆元。必要性:a简化剩余则a可逆a简化剩余(a,m)=1axmodm=1有惟一解a’,即aa’modm=1a是可逆元。充分性:a可逆则a是简化剩余a可逆存在a’，使得aa’modm=1则方程axmodm=1有解，根据定理1的必要可知(a,m)

3、b即(a,m)

4、1故(a,m)=1例:xmod3=2xmod5=3xmod7=2m1=3m

5、2=5m3=7b1=2b2=3b3=2m=m1m2m3=357M1=m/m1=57M1’=Mi(mi)-1modmi=2M2=m/m2=37M2’=Mi(mi)-1modmi=1M3=m/m3=35M3’=Mi(mi)-1modmi=1x=(M1’M1b1+M2’M2b2+…+M’kMkbk)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=m1m2m3m4=

6、56711M1=m/m1=6711=462M1’=Mi(mi)-1modmi=3M2=m/m2=5711=385M2’=Mi(mi)-1modmi=1M3=m/m3=5611=330M3’=Mi(mi)-1modmi=1M4=m/m4=567=210M4’=Mi(mi)-1modmi=1x=(M1’M1b1+M2’M2b2+M’3M3b3+M’4M4b4)modm=(462*3*b1+385*1*b2+330*1*b3+210*1*b4)modmxmod5=b1xmod6=b2xmod7=b3xmod11=b4m1=5m2=6m3=7m4=11

7、M1=m/m1=6711=462M1’M1modm1=1M2=m/m2=5711=385M2’M2modm2=1M3=m/m3=5611=330M3’M3modm3=1M4=m/m4=567=210M4’M4modm4=1M1’M1modm1=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

8、*92)=1462*3+5*(1+2*92-462)=1M1’=3例3xmod5=1xmod6=5xmod7=4xmod11=10x=(M1’M1b1+M2’M2b2+M’3M3b3+M’4M4b4)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+1…mk)=1….(1)(mi,Mi)=1故Mixmodmi=1有

9、解Mi’MiMi’modmi=1从(1)可知当ji时mj

10、Mi则Mimodmj=0(M1’M1a1+M2’M2a2+…+M’jMjaj+...+M’kMkak)modmj=M’jMjajmodmi=ajmodmi.xmodmi=aimodmi即满足方程。证明:惟一性，同一等价类的数看成一个根若x1,x2均是方程的根,x1modmi=aimodmi=x2modmim=m1m2..mk又m1,m2,…,mk两两互素则x1modm=x2modmx1,x2同属一个同余类，即是同一解。21000000mod77=?解二77