模线性方程与模线性方程组

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版标题样式,模线性方程,模线性方程组,henu,08wangnan,今天要解决的问题：,axb,(mod n),a0 n0,x=?,如：,4x2(mod 5),xa1(mod n1),xa2(mod n2),a0 n0,x=?,如：,x2(mod 5),x3(mod 13),求解模线性方程？,axb,(mod n),a0 n0,x=?,如：,4x2(mod 5),1.,是否有解？,2.,有几个解？,3.,这些解分别是多少？,？,分析,首先明确一点,如果,x,是解,(0=x0 n0,x=?,如：,x2(mod 5),x3(mod 13),韩信点兵！,在中国数学史上，广泛流传着一个“韩信点兵”的故事：,韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让 敌人知道自己部队的实力，,先令士兵从,1,至,3,报数，然后记下最后一个士兵所报之数；再令士兵从至报数，也记下最后一个士兵所报之数；最后令士兵从,1,至,7,报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，,而敌人则始终无法弄清他的部队究竟有多少名士兵。,韩信点兵！,在中国数学史上，广泛流传着一个“韩信点兵”的故事：,这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的,一次同余式解法,。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。,孙子算经？解模线性方程组！,最早提出并记叙这个数学问题的，是南北朝时期的数学著作,孙子算经,中的“物不知数”题目。这道“,物不知数,”的题目是这样的：,“今有一些物不知其数量。,如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。问：这些物一共有多少？,”,用简练的数学语言来表述就是：,求这样一个数，使它被除余，被除余，被除余。,x 2(mod 3),x 3(mod 5),x 2(mod 7),X=?,中国剩余定理,考虑方程组,x,a,i,(mod,m,i,),m,i,两两互素,在,0=xM=m,1,m,2,m,k,内有唯一解,记,M,i,=M/m,i,，则,(,M,i,m,i,)=1,存在,p,i,q,i,，,M,i,p,i,+m,i,q,i,=1,记录,e,i,=,M,i,p,i,，,则,j=i,时,e,i,1(mod,m,j,),ji,时,e,i,0(mod,m,j,),则,e,1,a,1,+e,2,a,2,+,e,k,a,k,就是一个解,调整得到,0,m),内的唯一解（想一想，如何调整）,整理一下,一般线性方程组,a,i,x,i,b,i,(mod,n,i,),ax,b,(mod,n,),x,b,1,(mod,n,1,),x,b,1,(mod,n,1,),x,b,1,(mod,p,1,i,),用中国剩余定理,其他规则同余方程,二项方程,:,借助离散对数,(,本身,?),高次方程,:,分解,n,降幂,单个多变元线性方程,:,消法,求解模线性方程组步骤：,找到模线性方程组中每个方程的,a,i,，,n,i,求出相对应的,m,i,m,i,-1,求出相应的,c,i,=m,i,(m,i,-1,mod,n,i,),最后一步：,a (a,1,c,1,+a,2,c,2,+,a,k,c,k,)(mod n),x 2(mod 3),x 3(mod 5),x 2(mod 7),x=?,a,1,=2 n,1,=3,a,2,=3 n,2,=5,a,3,=2 n,3,=7,n=n,1,*n,2,*n,3,=105,m,1,=35 m,1,-1,=2,m,2,=21 m,2,-1,=1,m,3,=15 m,3,-2,=1,a=23+k*,n(k,=0,1,2),练习：,Poj,1006,