輾轉相除原理

歐幾里德算法又稱輾轉相除法，是指用於計算兩個非負整數a，b的最大公約數。應用領域有數學和計算機兩個方面。計算公式gcd(a，b) = gcd(b，a mod b)。

其計算原理依賴於下面的定理：

定理：兩個整數的最大公約數等於其中較小的那個數和兩數相除餘數的最大公約數。最大公約數（Greatest Common Divisor）縮寫爲GCD。

gcd(a，b) = gcd(b，a mod b) (不妨設a>b 且r=a mod b ，r不爲0)

證法一

a可以表示成a = kb + r（a，b，k，r皆爲正整數，且r

假設d是a，b的一個公約數，記作d|a，d|b，即a和b都可以被d整除。

而r = a - kb，兩邊同時除以d，r/d=a/d-kb/d=m，由等式右邊可知m爲整數，因此d|r

因此d也是b，a mod b的公約數

假設d是b，a mod b的公約數， 則d|b，d|(a-k*b)，k是一個整數。

進而d|a.因此d也是a，b的公約數

因此(a，b)和(b，a mod b)的公約數是一樣的，其最大公約數也必然相等，得證。

證法二

第一步：令c=gcd(a，b)，則設a=mc，b=nc

第二步：可知r =a-kb=mc-knc=(m-kn)c

第三步：根據第二步結果可知c也是r的因數

第四步：可以斷定m-kn與n互素【否則，可設m-kn=xd，n=yd，(d>1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)dc，b=nc=ycd，故a與b最大公約數≥cd，而非c，與前面結論矛盾】

從而可知gcd(b，r)=c，繼而gcd(a，b)=gcd(b，r)，得證

注意:兩種方法是有區別的。

假設有兩個數x和y，存在一個最大公約數z=(x，y)，即x和y都有公因數z，那麼x一定能被z整除，y也一定能被z整除，所以x和y的線性組合mx±ny也一定能被z整除。（m和n可取任意整數）對於輾轉相除法來說，思路就是：若x>y，設x/y=n餘c，則x能表示成x=ny+c的形式，將ny移到左邊就是x-ny=c，由於一般形式的mx±ny能被z整除，所以等號左邊的x-ny（作爲mx±ny的一個特例）就能被z整除，即x除y的餘數c也能被z整除。

若不能整除，則將min{x，y}作爲被除數，餘數c作爲除數，繼續循環這個過程，直到餘數c=0爲止。爲什麼這樣做可以得到結果因爲在這個過程中，被除數和除數最大公約數始終沒有變。分析如下：

設商爲f，假設第十一步得到了結果，循環過程：x/y=f1…c1y/c1=f2…c2c1/c2=f3…c3……c8/c9=f10…c10c9/c10=f11…0如此，c10即爲最大公約數。那麼據第一段所述，可得：c9%c10=0，c8%c10=0，c7%c10=0……c1%c10=0，據此可說明被除數和除數最大公約數始終沒有變。於是這樣就得到了最大公約數了。

備註：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數最小公倍數等於兩個數的乘積除以最小公約數b能被a整除<=>b/a=c…0 (c爲整數)b能整除a<=>a/b=c’…0(c爲整數).