歐幾里得算法數(shù)學(xué)算法01算法簡(jiǎn)介算法原理算法版本計(jì)算證明程序設(shè)計(jì)目錄03050204基本信息歐幾里得算法又稱(chēng)輾轉(zhuǎn)相除法，是指用于計(jì)算兩個(gè)非負(fù)整數(shù)a，b的最大公約數(shù)。應(yīng)用領(lǐng)域有數(shù)學(xué)和計(jì)算機(jī)兩個(gè)方面。計(jì)算公式gcd(a,b)=gcd(b,amodb)。歐幾里得算法和擴(kuò)展歐幾里得算法可使用多種編程語(yǔ)言實(shí)現(xiàn)。算法簡(jiǎn)介算法簡(jiǎn)介歐幾里得算法是用來(lái)求兩個(gè)正整數(shù)最大公約數(shù)的算法。古希臘數(shù)學(xué)家歐幾里得在其著作《TheElements》中最早描述了這種算法,所以被命名為歐幾里得算法。擴(kuò)展歐幾里得算法可用于RSA加密等領(lǐng)域。假如需要求1997和615兩個(gè)正整數(shù)的最大公約數(shù),用歐幾里得算法，是這樣進(jìn)行的：1997÷615=3(余152)615÷152=4(余7)152÷7=21(余5)7÷5=1(余2)5÷2=2(余1)2÷1=2(余0)至此，最大公約數(shù)為1計(jì)算證明證法二證法一計(jì)算證明證法一a可以表示成a=kb+r（a，b，k，r皆為正整數(shù)，且r不為0）假設(shè)d是a,b的一個(gè)公約數(shù)，記作d|a,d|b，即a和b都可以被d整除。而r=a-kb，兩邊同時(shí)除以d，r/d=a/d-kb/d，由等式右邊可知m=r/d為整數(shù)，因此d|r因此d也是b,amodb的公約數(shù)。因(a,b)和(b,amodb)的公約數(shù)相等，則其最大公約數(shù)也相等，得證。證法二假設(shè)c=gcd(a,b),則存在m,n，使a=mc,b=nc;令r=amodb，即存在k，使r=a-kb=mc-knc=(m-kn)c;故gcd(b,amodb)=gcd(b,r)=gcd(nc,(m-kn)c)=gcd(n,m-kn)c;則c為b與amodb的公約數(shù);假設(shè)d=gcd(n,m-kn),則存在x,y,使n=xd,m-kn=yd;故m=yd+kn=yd+kxd=(y+kx)d;故有a=mc=(y+kx)dc,b=nc=xdc;可得gcd(a,b)=gcd((y+kx)dc,xdc)=dc;由于gcd(a,b)=c,故d=1;即gcd(n,m-kn)=1,故可得gcd(b,amodb)=c;故得證gcd(a,b)=gcd(b,amodb).注意:兩種方法是有區(qū)別的。算法原理算法原理Lemma1.3.1若a,b且a=bh+r，其中h,r，則gcd(a,b)=gcd(b,r)。

證明.假設(shè)d1=gcd(a,b)且d2=gcd(b,r)，證明d1|d2且d2|d1，因而可利用Proposition1.1.3⑵以及d1,d2皆為正數(shù)得證d1=d2。因d1|a且d1|b利用Corollary1.1.2知d1|a-bh=r.因?yàn)閐1|b,d1|r且d2=gcd(b,r)故由Proposition1.2.5知d1|d2.另一方面，因?yàn)閐2|b且d2|r故d2|bh+r=a.因此可得d2|d1。Lemma1.3.1告訴當(dāng)a>b>0時(shí)，要求a,b的最大公因數(shù)我們可以先將a除以b所得余數(shù)若為r，則a,b的最大公因數(shù)等于b和r的最大公因數(shù).因?yàn)閞<b<a，所以當(dāng)然把計(jì)算簡(jiǎn)化了，接著我們就來(lái)看看輾轉(zhuǎn)相除法.由于gcd(a,b)=gcd(-a,b)所以我們只要考慮a,b都是正整數(shù)的情況。Theorem1.3.2(TheEuclideanAlgorithm)假設(shè)a,b且a>b.由除法原理知存在h0,r0使得歐幾里得算法a=bh0+r0，其中r0<b.若r0>0，則存在h1,r1使得b=r0h1+r1，其中0r1<r0.程序設(shè)計(jì)程序設(shè)計(jì)輾轉(zhuǎn)相除法是利用以下性質(zhì)來(lái)確定兩個(gè)正整數(shù)a和b的最大公因子的：⒈若r是a÷b的余數(shù)，且r不為0，則gcd(a,b)=gcd(b,r)⒉a和其倍數(shù)之最大公因子為a。另一種寫(xiě)法是：⒈令r為a/b所得余數(shù)（0≤r若r=0，算法結(jié)束；b即為答案。⒉互換：置a←b，b←r，并返回第一步。算