《剩余定理公式》PPT課件

《《剩余定理公式》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、中國剩余定理今有物不知其數(shù)，三三數(shù)之有二，五五數(shù)之有三，七七數(shù)之有二，問物有多少？解答：三三數(shù)之有二對(duì)應(yīng)140，五五數(shù)之有三對(duì)應(yīng)63，七七數(shù)之有二對(duì)應(yīng)30，這些數(shù)相加得到233，再減210，即得數(shù)23。同余方程式：xmod3=2xmod5=3xmod7=22?5?7?2=1401?3?7?3=631?3?5?2=302?3?5?7=210定理1設(shè)m1,m2,…mk是兩兩互素的正整數(shù)，則對(duì)任意b1,b2,…,bk，同余方程組xmodm1=b1modm1,xmodm2=b2modm2,…xmodmk=bkmodmk,其解為：x=(M1’M1b1+M2’M2b2+…+M’kMkbk)modmm

2、=m1m2…mk,復(fù)習(xí)Mi=m/miMiMi’modmi=1顯然(Mi,mi)=1即Mi’是Mi的逆元Mi?(mi)-1modmi或者可用輾轉(zhuǎn)相除法求Mi’.定理4:m?Z+,a?Z,a是模m簡(jiǎn)化剩余的充要條件a是模m的可逆元。必要性:a簡(jiǎn)化剩余則a可逆a簡(jiǎn)化剩余?(a,m)=1?axmodm=1有惟一解a’,即aa’modm=1?a是可逆元。充分性:a可逆則a是簡(jiǎn)化剩余a可逆?存在a’，使得aa’modm=1?則方程axmodm=1有解，根據(jù)定理1的必要可知(a,m)

3、b即(a,m)

4、1故(a,m)=1例:xmod3=2xmod5=3xmod7=2m1=3m2=5m3=7b1=2b2=

5、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=5?6?7?11M1=m/m1=6?7?1

6、1=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=11M1=m/m1=6?7?11=462M1’M1modm1

7、=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最大公約數(shù)為1，M1’,k’為組合系數(shù)?利用輾轉(zhuǎn)相除法求最大約數(shù),然后求組合系數(shù)。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

8、例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證明:驗(yàn)證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有解Mi’MiMi’modmi=1從(1)可知當(dāng)j?i時(shí)mj

9、Mi則Mimodmj=0

10、(M1’M1a1+M2’M2a2+…+M’jMjaj+...+M’kMkak)modmj=M’jMjajmodmi=ajmodmi.xmodmi=aimodmi即滿足方程。證明:惟一性，同一等價(jià)類的數(shù)看成一個(gè)根若x1,x2均是方程的根,x1modmi=aimodmi=x2modmim=m1m2..mk又m1,m2,…,mk兩兩互素則x1modm=x2modmx1,x2同屬一個(gè)同余類，即是同一解。21000000mod77=?解二77