《剩余定理公式》PPT课件

《剩余定理公式》PPT课件

ID:37286439

大小:380.31 KB

页数:13页

时间:2019-05-12

《剩余定理公式》PPT课件_第1页
《剩余定理公式》PPT课件_第2页
《剩余定理公式》PPT课件_第3页
《剩余定理公式》PPT课件_第4页
《剩余定理公式》PPT课件_第5页
资源描述:

《《剩余定理公式》PPT课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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’kMkbk)modmm

2、=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=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最大公约数为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

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证明:验证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)可知当ji时mj

9、Mi则Mimodmj=0

10、(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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。