生动讲解中国剩余定理.ppt_第1页
生动讲解中国剩余定理.ppt_第2页
生动讲解中国剩余定理.ppt_第3页
生动讲解中国剩余定理.ppt_第4页
生动讲解中国剩余定理.ppt_第5页
已阅读5页，还剩7页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

孙子定理TheChineseRemainderTheorem,韩信点兵韩信带贰仟伍佰士兵出去打仗，回营后，刘邦问士兵人数。韩信让士兵先列成五行纵队，末行一人；列成六行纵队，末行五人；列成七行纵队，末行四人；列成十一行纵队，末行十人。韩信立刻回答二千一百一十一人。刘邦惊为天人！,从“韩信点兵”谈起,物不知数问题孙子算经,孙武公元前551-前479,物不知数问题的解,v,v,公式表示：140+63+30=233233-210=23关键参数：702115,v,v,v,v,关键参数分析,x2(mod3);x3(mod5);x2(mod7),21,15,0,1,0,0,0,1,问题求解,因为3,5,7=105,任意105的倍数都被3,5,7整除，故,233+105n均是答案,233,2+0+0=2,0+0+2=2,0+3+0=3,213=63,0,3,0,152=30,0,0,2,孙子定理设m1,m2,mk是k个两两互素的正整数，m=m1m2mk,Mi=m/mi(i=1,k),则同余方程组xb1(modm1);xb2(modm2);xbk(modmk)有唯一解xM1N1b1+M2N2b2+MkNkbk(modm)其中MiNi1(modmi)(i=1,k)。,孙子定理,N1,N2,Nk,证明：因为(mi,mj)=1,ij,则(Mi,mi)=1,对每个Mi，都存在Ni,使得MiNi1(modmi)又m=miMi,故mj|Mi,ij,即MiNi0(modmj)则M1N1b1+M2N2b2+MkNkbkbi(modmi).因此xM1N1b1+M2N2b2+MkNkbk(modm)是同余方程的整数解。,孙子定理的证明,如果y也是上述同余方程的解，则满足xy(modm1);xy(modm2);xy(modmk)即m1|(x-y),m2|(x-y),mk|(x-y).所以m|(x-y)即xy(modm).即证方程在模m条件下有唯一解。,唯一性证明,解：应用孙子定理m1=5,m2=6,m3=7,m4=11;b1=1,b2=5,b3=4,b4=10;m=56711=2310;,“韩信点兵”问题的求解,解一次同余方程组x1(mod5);x5(mod6);x4(mod7);x10(mod11),M1=462,M2=385,M3=330,M4=210;N1=3,N2=1,N3=1,N4=1;x4623+3855+3304+2101067312111(mod2310),南宋秦九韶对“物不知数”问题进行推广，得到求解一次同余方程组的一般方法，定名“大衍求一术”。欧拉和高斯在研究一次同余式问题时，得到与秦九韶“大衍求一术”相同的定理，因此被国外学者称为“中国剩余定理”。近世代数的发展
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论