《初等数论简介》PPT课件.ppt

初等数论简介,LiTao,我想分五个部分讲：一个关于最大公约数的定理，欧里几德算法，线性不定方程，模线性方程，最后中国剩余定律。,两个非零整数a,b的最大公约数(gcd(a,b)是a,b的最小正线性组合。譬如9和15的最大公约数为3=9*2+15*(-1)；5和4的最大公约数为1=5*1+4*(-1)；-3和5的最大公约数为1=-3*（-2）+5*(-1)；两个互质整数的最小正线性组合为1.证明详见算法导论P524,欧里几德算法,对于任意非负整数a和任意正整数b,gcd(a,b)=gcd(b,amodb)；欧里几德求a,b的最大公约数EUCLID(a,b)if(b=0)thenreturna;elsereturnEUCLID(b,amodb).譬如EUCLID（30，21）=EUCLID（21，9）=EUCLID（9，3）=EUCLID（3，0）=3；,扩展的欧几里得算法,刚才的算法可以求得a,b最大公约数d,但我还想知道d如何用a,b的线性组合表示。即我想知道d=a*x+b*y中x和y的值。易知d=b*x+(amodb)*y,我们可以发现x,y和x,y的关系x=y;y=x-(a/b)*y;(a/b取下整数,下同）我们来证明因为amodb=a-(a/b)*b;所以d=b*x+(a-(a/b)*b)*y;=d=a*y+b*(x-(a/b)*y);证毕。由于欧几里得算法最后一步为EUCLID（a,0)d=a*1+0*0,即x=1,y=0,由此逐步向上可算得x,y.,伪代码（修改一下刚才的代码即可）EXTENDED-EUCLID(a,b)ifb=0thenreturn(a,1,0);(d,x,y)EXTENDED-EUCLID(b,amodb);(d,x,y)(d,y,x-(a/b)*y);return(d,x,y);,线性不定方程,初中学过方程a*x+b*y=c有无数对解，我们现在要研究的是他是否有整数解。所以我们也可以把他看成a,b这样的线性组合是否存在。最大公约数d=a*s+b*t,因为d|a且d|b所以d|a*x+b*y,所以必然d|c。所以c如果不是d的整数倍，则方程肯定无整数解。当d|c时，显然x0=s*(c/d)，y0=t*(c/d)是方程的整数解。s和t都可以通过扩展的欧几里德算得。我们进一步可以发现x=x0+(b/d)*n,y=y0-(a/d)*n;都是方程的解。最后还可以证明方程所有的解都具有上面的形式。因为a*x0+b*y0=c;=(ax+by)-(ax0+by0)=0=a(x-x0)=b(y0-y)=(a/d)(x-x0)=(b/d)(y0-y)=x-x0=(b/d)(y0-y)/(a/d);因为x-x0为整数，b/d与a/d互质，所以y0-y=(a/d)*n;即y=y0-(a/d)*n,同理x=x0+(b/d)*n;,模线性方程,ab(modm)表示amodm等于bmodm,即a-km=b(kZ);我们可以把模线性方程axb(modm)转化为线性不定方程来求出他的解。axb(modm)ax-my=b如果b不能被d整除，则无解。如果d|b,x=x0+(m/d)*n;,中国剩余定律,解模线性方程组：xa1(modm1),xa2(modm2),.xar(modmr),(m1,m2.mr为两两互质的正整数，令M=m1*m2*.*mr,Mk=M/mk,