欧几里德算法的简单解释

[编辑本段]欧几里得算法的概述欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理：定理：gcd(a,b)=gcd(b,amodb)证明：a可以表示成a=kb+r，则r=amodb假设d是a,b的一个公约数，则有d|a,d|b，而r=a-kb，所以d|r所以d是(b,amodb)的公约数假设d是(b,amodb)的公约数，则d|b，d|r，但是a=kb+r所以d也是(a,b)的公约数所以(a,b)和(b,amodb)的公约数是一样的，其最大公约数也必然相等，得证[编辑本段]欧几里得算法原理Lemma1.3.1若a,b且a=bh+r,其中h,r,则gcd(a,b)=gcd(b,r).证明.假设d1=gcd(a,b)且d2=gcd(b,r).我们证明d1|d2且d2|d1,因而可利用Proposition1.1.3(2)以及d1,d2皆为正数得证d1=d2.因d1|a且d1|b利用Corollary1.1.2我们知d1|a-bh=r.因为d1|b,d1|r且d2=gcd(b,r)故由Proposition1.2.5知d1|d2.另一方面,因为d2|b且d2|r故d2|bh+r=a.所以可得d2|d1.Lemma1.3.1告诉我们当a>b>0时,要求a,b的最大公因数我们可以先将a除以b所得馀数若为r,则a,b的最大公因数等于b和r的最大公因数.因为0rb.由除法原理我们知存在h0,r0使得a=bh0+r0,其中0r00,则存在h1,r1使得b=r0h1+r1,其中0r10,则存在h2,r2使得r0=r1h2+r2,其中0r2r1>r2>...是严格递减的,因为r0和0之间最多仅能插入r0-1个正整数,所以我们知道一定会有nr0使得rn=0.若r0=0,即a=bh0,故知b为a之因数,得证b为a,b的最大公因数.若r0>0,则由Lemma1.3.1知gcd(a,b)=gcd(b,r0)=gcd(r0,r1)=...=gcd(rn-1,rn)=gcd(rn-1,0)=rn-1.现在我们来看用辗转相除法求最大公因数的例子Example1.3.3我们求a=481和b=221的最大公因数.首先由除法原理得481=2.221+39,知r0=39.所以再考虑b=221除以r0=39得221=5.39+26,知r1=26.再以r0=39除以r1=26得39=1.26+13,知r2=13.最后因为r2=13整除r1=26知r3=0,故由Theorem1.3.2知gcd(481,221)=r2=13.在利用辗转相除法求最大公因数时,大家不必真的求到rn=0.例如在上例中可看出r0=39和r1=26的最大公因数是13,利用Lemma1.3.1马上得知gcd(a,b)=13.在上一节Corollary1.2.5告诉我们若gcd(a,b)=d,则存在m,n使得d=ma+nb.当时我们没有提到如何找到此m,n.现在我们利用辗转相除法来介绍一个找到m,n的方法.我们沿用Theorem1.3.2的符号.首先看r0=0的情形,此时d=gcd(a,b)=b所以若令m=0,n=1,则我们有d=b=ma+nb.当r00但r1=0时,我们知d=gcd(a,b)=r0.故利用a=bh0+r0知,若令m=1,n=-h0,则d=r0=ma+nb.同理若r00,r10但r2=0,则知d=gcd(a,b)=r1.故利用a=bh0+r0以及b=r0h1+r1知r1=b-r0h1=b-(a-bh0)h1=-h1a+(1+h0h1)b.所以若令m=-h1且n=1+h0h1,则d=r1=ma+nb.依照此法,当r0,r1和r2皆不为0时,由于d=gcd(a,b)=rn-1故由rn-3=rn-2hn-1+rn-1知d=rn-3-hn-1rn-2.利用前面推导方式我们知存在m1,m2,n1,n2使得rn-3=m1a+n1b且rn-2=m2a+n2b故代入得d=(m1a+n1b)-hn-1(m2a+n2b)=(m1-hn-1m2)a+(n1-hn-1n2)b.所以若令m=m1-hn-1m2且n=n1-hn-1n2,则d=ma+nb.上面的说明看似好像当r00时对每一个i{0,1,...,n-2}要先将ri写成ri=mia+nib,最后才可将d=rn-1写成ma+nb的形式.其实这只是论证时的方便,在实际操作时我们其实是将每个ri写成mi'ri-2+ni'ri-1的形式慢慢逆推回d=ma+nb.请看以下的例子.Example1.3.4我们试着利用Example1.3.3所得结果找到m,n使得13=gcd(481,221)=481m+221n.首先我们有13=r2=39-26=r0-r1.而r1=221-5.39=b-5r0,故得13=r0-(b-5r0)=6r0-b.再由r0=481-2.221=a-2b,得知13=6(a-2b)-b=6a-13b.故得m=6且n=-13会满足13=481m+221n.要注意这里找到的m,n并不会是唯一满足d=ma+nb的一组解.虽然上面的推演过程好像会只有一组解,不过只能说是用上面的方法会得到一组解,并不能担保可找到所有的解.比方说若令m'=m+b,n'=n-a,则m'a+n'b=(m+b)a+(n-a)b=ma+nb=d.所以m',n'也会是另一组解.所以以后当要探讨唯一性时,若没有充分的理由千万不能说由前面的推导过程看出是唯一的就断言是唯一.一般的作法是假设你有两组解,再利用这两组解所共同满足的式子找到两者之间的关系.我们看看以下的作法.Proposition1.3.5假设a,b且d=gcd(a,b).若x=m0,y=n0是d=ax+by的一组整数解,则对任意t,x=m0+bt/d,y=n0-at/d皆为d=ax+by的一组整数解,而且d=ax+by的所有整数解必为x=m0+bt/d,y=n0-at/d其中t这样的形式.证明.假设x=m,y=n是d=ax+by的一组解.由于已假设x=m0,y=n0也是一组解,故得am+bn=am0+bn0.也就是说a(m-m0)=b(n0-n).由于d=gcd(a,b),我们可以假设a=a'd,b=b'd其中a',b'且gcd(a',b')=1(参见Corollary1.2.3).所以得a'(m-m0)=b'(n0-n).利用b'|a'(m-m0),gcd(a',b')=1以及Proposition1.2.7(1)得b'|m-m0.也就是说存在t使得m-m0=b't.故知m=m0+b't=m0+bt/d.将m=m0+bt/d代回am+bn=am0+bn0可得n=n0-at/d,所以得证d=ax+by的整数解都是x=m0+bt/d,y=n0-at/d其中t这样的形式.最后我们仅要确认对任意t,x=m0+bt/d,y=n0-at/d皆为d=ax+by的一组整数解.但是将x=m0+bt/d,y=n0-at/d代入ax+by得a(m0+bt/d)+b(n0-at/d)=am0+bn0=d,故得证本定理.利用Proposition1.3.5我们就可利用Example1.3.4找到13=481x+221y的一组整数解x=6,y=-13得到x=6+17t,y=-13-37t其中t是13=481x+221y所有的整数解

985大学 211大学 全国院校对比 专升本 美国留学 留求艺网