《初等数论简介》PPT课件

《《初等数论简介》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、初等数论简介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)；欧里几

2、德求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取下整数

3、,下同）我们来证明因为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)

4、*y');return(d,x,y);线性不定方程初中学过方程a*x+b*y=c有无数对解，我们现在要研究的是他是否有整数解。所以我们也可以把他看成a,b这样的线性组合是否存在。最大公约数d=a*s+b*t,因为d

5、a且d

6、b所以d

7、a*x+b*y,所以必然d

8、c。所以c如果不是d的整数倍，则方程肯定无整数解。当d

9、c时，显然x0=s*(c/d)，y0=t*(c/d)是方程的整数解。s和t都可以通过扩展的欧几里德算得。我们进一步可以发现x=x0+(b/d)*n,y=y0-(a/d)*n;都是方程的解。最后还可

10、以证明方程所有的解都具有上面的形式。因为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;模线性方程a≡b(modm)表示amodm等于bmodm,即a-km=b(k∈Z);我们可以把模线性方程ax≡b(modm)转化为线性不定方程来求

11、出他的解。ax≡b(modm)<=>ax-my=b如果b不能被d整除，则无解。如果d

12、b,x=x0+(m/d)*n;中国剩余定律解模线性方程组：x≡a1(modm1),x≡a2(modm2),.....x≡ar(modmr),(m1,m2...mr为两两互质的正整数，令M=m1*m2*...*mr,Mk=M/mk,由方程Mk*yk≡1(modmk)求得yk.)方程有唯一解x≡a1M1y1+a2M2y2+...arMryr(modM);证明详见《初等数论及其应用》P145