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

初等数论简介,Li Tao,我想分五个部分讲：一个关于最大公约数的定理，欧里几德算法，线性不定方程，模线性方程，最后中国剩余定律。,两个非零整数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,a mod b)； 欧里几德求a,b的最大公约数 EUCLID(a,b) if(b=0) then return a; else return EUCLID(b,a mod b). 譬如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+(a mod b)*y,我们可以发现x,y和x,y的关系 x=y; y=x-(a/b)*y;(a/b取下整数,下同） 我们来证明 因为a mod b=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) if b=0 then return (a,1,0); (d,x,y)EXTENDED-EUCLID(b,a mod b); (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(mod m)表示a mod m等于b mod m,即a-km=b(kZ); 我们可以把模线性方程axb(mod m)转化为线性不定方程来求出他的解。 axb(mod m)ax-my=b 如果b不能被d整除，则无解。 如果d|b,x=x0+(m/d)*n;,中国剩余定律,解模线性方程组： xa1(mod m1), xa2(mod m2), . . . . . xar(mod mr), (m1,m2.mr为两两互质的正整数，令M=m1*m2*.*mr,Mk=M/mk,由