輾轉(zhuǎn)相除法原本是初等數(shù)論的內(nèi)容,不過近年在中學(xué)數(shù)學(xué)里也有出現(xiàn),是以算法初步的內(nèi)容出現(xiàn)的,所以有必要簡單介紹一下.并且我們在下一篇文章里,將結(jié)合菲波拉契數(shù)列導(dǎo)出輾轉(zhuǎn)相除法的步數(shù)估計——拉梅定理.
　　輾轉(zhuǎn)相除法又叫歐幾里得算法,是歐幾里得最先提出來的.不過這個名字有點不好,就如同在數(shù)學(xué)里說歐拉定理這個詞一樣,你不知道說的是哪個定理,因為歐拉發(fā)現(xiàn)的定理實在是太多……輾轉(zhuǎn)相除法的實現(xiàn),是基于下面的原理(在這里用(a,b)表示a和b的最大公因數(shù))：
　　(a,b)=(a,ka+b),其中a、b、k都為自然數(shù).………………①
　　也就是說,兩個數(shù)的最大公約數(shù),將其中一個數(shù)加到另一個數(shù)上,得到的新數(shù),其公約數(shù)不變,比如(4,6)=(4+6,6)=(4,6+2×4)=2.要證明這個原理很容易：如果p是a和ka+b的公約數(shù),p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公約數(shù),從而證明他們的最大公約數(shù)也是相等的.
　　基于上面的原理,就能實現(xiàn)我們的迭代相減法：
　　(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2
　　基本上思路就是大數(shù)減去小數(shù),一直減到能算出來為止,在作為練習(xí)的時候,往往進行到某一步就已經(jīng)可以看出得值.迭代相減法簡單,不過步數(shù)比較多,實際上我們可以看到,在上面的過程中,由(78,14)到(8,14)完全可以一步到位,因為(78,14)=(14×5+8,14)=(8,14),由此就誕生出我們的輾轉(zhuǎn)相除法.
　　用輾轉(zhuǎn)相除法求(a,b).設(shè)r0=b,r1=a,反復(fù)運用除法算式,得到一系列整數(shù)qi,ri和下面的方程：
　　相當于每一步都運用原理①把數(shù)字進行縮小,上面右邊就是每一步對應(yīng)的縮小結(jié)果,可以看出,最后的余數(shù)rn就是a和b的公約數(shù).我們以一個題為例說明基本過程.
　　例題：求(326,78)
　　所以(326,78)=2.這和我們用迭代相減法算出來的結(jié)果是一樣的.所以中學(xué)的同學(xué)們應(yīng)該看到,迭代相減法和輾轉(zhuǎn)相除法在本質(zhì)上是一樣的,相對來說,減法比較簡單,但是除法步數(shù)少.
　　我們要看到的是,在輾轉(zhuǎn)相除法中,我們必須算到最后一步才知道rn是不是所求的最大公因數(shù),所以我們把n稱作輾轉(zhuǎn)相除法里的步數(shù).在明天,我們將利用輾轉(zhuǎn)相除法的過程來導(dǎo)出此方法的步數(shù)估計——拉梅定理.