《《初等数论简介》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《初等数论简介》PPT课件.ppt（9页珍藏版）》请在装配图网上搜索。
1、初等数论简介 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的最
2、大公约数 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取下整数 ,下同） 我们来证明 因
3、为 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
4、有无数对解，我们现在要研究的是他是否 有整数解。 所以我们也可以把他看成 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-
5、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,由方程 Mk*yk1(mod mk) 求得 yk.) 方程有唯一解 xa1M1y1+a2M2y2+.arMryr(mod M); 证明详见初等数论及其应用 P145
《初等数论简介》PPT课件.ppt
