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

孙子定理The Chinese Remainder Theorem,韩信点兵 韩信带贰仟伍佰士兵出去打仗，回营后，刘邦问士兵人数。韩信让士兵先列成五行纵队，末行一人；列成六行纵队，末行五人；列成七行纵队，末行四人；列成十一行纵队，末行十人。韩信立刻回答二千一百一十一人。刘邦惊为天人！,从“韩信点兵”谈起,物不知数问题 孙子算经,孙武 公元前551-前479,物不知数问题的解,v,v,公式表示：140+63+30=233233-210=23 关键参数：70 21 15,v,v,v,v,关键参数分析,x 2(mod3);x 3(mod5);x 2(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),则同余方程组x b1(mod m1);x b2(mod m2);x bk(mod mk)有唯一解x M1 N1b1+M2 N2b2+Mk Nk bk(mod m)其中MiNi1(mod mi)(i=1,k)。,孙子定理,N1,N2,Nk,证明：因为(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(mod 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),南宋秦九韶对“物不知数”问题进行推广，得到求解一次同余方程组的一般方法，定名“大衍求一术”。欧拉和高斯在研究一次同余式问题时，得到与秦九韶“大衍求一术”相同的定理，因此被国外学者称为“中国剩余定理”。近世代数的发展赋予中国剩余定理更崭新的生命，不仅可以解决整数同余问题，还可以推广到一般交换环中。,孙子定理的推广中国剩余定理,谢 谢！,