生动讲解中国剩余定理.ppt

《生动讲解中国剩余定理.ppt》由会员分享，可在线阅读，更多相关《生动讲解中国剩余定理.ppt（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、孙子定理孙子定理The Chinese Remainder TheoremThe Chinese Remainder Theorem韩信点兵 韩信带贰仟伍佰士兵出去打仗，回营后，刘邦问士兵人数。韩信让士兵先列成五行纵队，末行一人；列成六行纵队，末行五人；列成七行纵队，末行四人；列成十一行纵队，末行十人。韩信立刻回答二千一百一十一人。刘邦惊为天人！从从“韩韩信点兵信点兵”谈谈起起物不知数物不知数问题问题 孙孙子算子算经经 孙武 公元前551-前479物不知数物不知数问题问题的解的解vv公公式表示式表示：140+63+30=233233-210=23 关键参数：70 21 15vvvvmod3同余

2、mod5同余mod7同余70100关关键键参数分析参数分析x 2(mod3);x 3(mod5);x 2(mod7)2115010001mod3同余mod5同余mod7同余702=140200问题问题求解求解因为3,5,7=105,任意105的倍数都被3,5,7整除，故233+105233+105n 均是答案均是答案2332+0+0=20+0+2=20+3+0=3213=63030152=3000 2孙子定理 设m1,m2,mk 是 k 个两两互素的正整数，m=m1m2mk,Mi=m/mi(i=1,k),则同余方程组x b1(mod m1);x b2(mod m2);x bk(mod mk)有

3、唯一解x M1 N1b1+M2 N2b2+Mk Nk bk(mod m)其中MiNi1(mod mi)(i=1,k)。孙子定理N1N2Nk证明：因为(mi,mj)=1,ij,则(Mi,mi)=1,对每个Mi，都存在Ni,使得MiNi 1(mod mi)又m=mi Mi,故mj|Mi ,ij,即MiNi0(mod mj)则M1 N1b1+M2 N2b2+Mk Nk bk bi(mod mi).因此 xM1 N1b1+M2 N2b2+Mk Nk bk (mod m)是同余方程的整数解。孙孙子定理的子定理的证证明明如果y也是上述同余方程的解，则满足xy(mod m1);xy(mod m2);xy(m

4、od mk)即m1|(x-y),m2|(x-y),mk|(x-y).所以m|(x-y)即xy(mod m).即证方程在模m条件下有唯一解。唯一性唯一性证证明明解：应用孙子定理m1=5,m2=6,m3=7,m4=11;b1=1,b2=5,b3=4,b4=10;m=56711=2310;“韩韩信点兵信点兵”问题问题的求解的求解解一次同余方程组x 1(mod5);x 5(mod6);x 4(mod7);x 10(mod11)M1=462,M2=385,M3=330,M4=210;N1=3,N2=1,N3=1,N4=1;x 4623+3855+3304+21010 6731 2111(mod2310)南宋秦九韶对“物不知数”问题进行推广，得到求解一次同余方程组的一般方法，定名“大衍求一术”。欧拉和高斯在研究一次同余式问题时，得到与秦九韶“大衍求一术”相同的定理，因此被国外学者称为“中国剩余定理”。近世代数的发展赋予中国剩余定理更崭新的生命，不仅可以解决整数同余问题，还可以推广到一般交换环中。孙孙子定理的推广子定理的推广中国剩余定理中国剩余定理 谢谢 谢！谢！