在求解最大公約數(shù)的幾種方法中,輾轉(zhuǎn)相除法最為出名。輾轉(zhuǎn)相除法是仍然在使用的歷史最悠久的算法之一。它首次出現(xiàn)于幾何原本(卷7命題1–2、卷10命題2–3)(大約公元前300年)。在卷7中用于整數(shù),在卷10中用于線段的長度(也就是所說的實數(shù),但是當時未有實數(shù)的概念)。卷10中出現(xiàn)的算法是幾何的,兩段線段a和b的最大公約數(shù)是準確測量a和b的最大長度。 這個算法可能并非歐幾里得發(fā)明,而僅僅是將先人的結(jié)果編進他的幾何原本。數(shù)學家、歷史學家范德瓦爾登認為卷7的內(nèi)容可能來自畢達哥拉斯學院出身的數(shù)學家寫的關于數(shù)論的教科書。輾轉(zhuǎn)相除法是被大約公元前375年的歐多克斯發(fā)現(xiàn)的,但也有可能更早之前就已經(jīng)存在,因為歐幾里得和亞里士多德的這兩位歷史名人著作中都出現(xiàn)了?νθυφα?ρεσι?一詞(anthyphairesis, 意為“輾轉(zhuǎn)相減”), 幾個世紀之后,輾轉(zhuǎn)相除法又分別被中國人和印度人獨立發(fā)現(xiàn),主要用來解天文學中用到的丟番圖方程以及指定準確的歷法。5世紀末,印度數(shù)學家、天文學家阿里亞哈塔可能是因為輾轉(zhuǎn)相除法在解丟番圖方程時的高效率而稱它為“粉碎機”。因為在中國,孫子算經(jīng)中出現(xiàn)了此算法的一個特例中國剩余定理,但是輾轉(zhuǎn)相除法的完整表述直到1247年秦九韶的數(shù)學九章中才出現(xiàn)。在歐洲,輾轉(zhuǎn)相除法首次出現(xiàn)于克勞德·巴希特(英語:Claude Gaspard Bachet de Méziriac)的著作Problèmes plaisants et délectables的第二版在歐洲,輾轉(zhuǎn)相除法廣泛使用于丟番圖方程和連分數(shù)。后來,英國數(shù)學家桑德森(英語:Nicholas Saunderson)將擴展歐幾里得算法作為羅杰科茨(英語:Roger Cotes)對計算連分數(shù)的方法的研究發(fā)表。 19世紀,輾轉(zhuǎn)相除法孕育出了一些新的數(shù)系,如高斯整數(shù)和艾森斯坦整數(shù)。1815年,高斯用輾轉(zhuǎn)相除法證明高斯整數(shù)的分解是惟一的,他的研究發(fā)表于1832年。高斯在他的《算數(shù)研究》(published 1801)中,作為處理連分數(shù)的方法提到了這個算法。約翰·狄利克雷是第一個將輾轉(zhuǎn)相除法作為數(shù)論的基礎的數(shù)學家。狄利克雷提出,數(shù)論中的很多結(jié)論,如分解的惟一性,在任何使輾轉(zhuǎn)相除法成立的數(shù)系中有效。狄利克雷的觀點被理查德·戴德金修改和推廣,他用輾轉(zhuǎn)相除法研究代數(shù)整數(shù)。戴德金是第一個用高斯整數(shù)的分解惟一性證明費馬平方和定理的數(shù)學家。戴德金還率先定義了歐幾里得整環(huán)的概念。19世紀末,輾轉(zhuǎn)相除法的輝煌逐漸被戴德金的理想取代。 輾轉(zhuǎn)相除法的其他應用發(fā)展于19世紀。1829年,施圖姆將輾轉(zhuǎn)相除法用于施圖姆序列(用于確定多項式的不同實根的個數(shù)的方法)。
輾轉(zhuǎn)相除法是歷史上第一個整數(shù)關系算法(英語:integer relation algorithm),即尋找兩數(shù)的整數(shù)關系的算法。近年來,出現(xiàn)了一些新穎的整數(shù)關系算法,如埃拉曼·弗格森(英語:Helaman Ferguson)和福爾卡德于1979年發(fā)表的弗格森-福爾卡德算法、以及與它相關的LLL算法(英語:Lenstra–Lenstra–Lovász lattice basis reduction algorithm)、HJLS算法以及PSLQ算法(英語:PSLQ algorithm)。
1969年,科爾(Cole)和戴維(Davie)基于輾轉(zhuǎn)相除法創(chuàng)造了一種二人游戲,叫做歐幾里得游戲。這個游戲有最優(yōu)策略。游戲開始于兩列分別為a和b個棋子組成的序列,玩家輪流從較長一列中取走較短一列棋子數(shù)量的m倍的棋子。如果兩列棋子a和b分別由x和y個棋子組成,其中x大于y,那么玩家可以序列a的棋子數(shù)量減少為自然數(shù)x ? my。最后率先將一列棋子清空的玩家勝出。 擴展歐幾里得算法
基本算法:對于不完全為 0 的非負整數(shù) a,b,gcd(a,b)表示 a,b 的最大公約數(shù),必然存在整數(shù)對 x,y ,使得 gcd(a,b)=ax+by。 證明:設 a>b。
1,顯然當 b=0,gcd(a,b)=a。此時 x=1,y=0;
2,ab≠0 時
設 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b);
則:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據(jù)恒等定理得:x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
上面的思想是以遞歸定義的,因為 gcd 不斷的遞歸求解一定會有個時候 b=0,所以遞歸可以結(jié)束。
歐幾里德算法是計算兩個數(shù)最大公約數(shù)的傳統(tǒng)算法,無論從理論還是從實際效率上都是很好的。但是卻有一個致命的缺陷,這個缺陷在素數(shù)比較小的時候一般是感覺不到的,只有在大素數(shù)時才會顯現(xiàn)出來。 Stein算法由J. Stein 1961年提出,這個方法也是計算兩個數(shù)的最大公約數(shù)。和歐幾里德算法算法不同的是,Stein算法只有整數(shù)的移位和加減法,這對于程序設計者是一個福音。
Stein算法:
設置A1=A、B1=B和C1=1
1、如果An=0,Bn*Cn是最大公約數(shù),算法結(jié)束
2、如果Bn=0,An*Cn是最大公約數(shù),算法結(jié)束
3、如果An和Bn都是偶數(shù),則An+1=An/2,Bn+1=Bn/2,Cn+1=Cn*2(注意,乘2只要把整數(shù)左移一位即可,除2只要把整數(shù)右移一位即可)
4、如果An是偶數(shù),Bn不是偶數(shù),則An+1=An/2,Bn+1=Bn,Cn+1=Cn (很顯然啦,2不是奇數(shù)的約數(shù))
5、如果Bn是偶數(shù),An不是偶數(shù),則Bn+1=Bn/2,An+1=An,Cn+1=Cn (很顯然啦,2不是奇數(shù)的約數(shù))
6、如果An和Bn都不是偶數(shù),則An+1=|An-Bn|,Bn+1=min(An,Bn),Cn+1=Cn
7、n加1,轉(zhuǎn)步驟1
考慮歐幾里德算法,最惡劣的情況是,每次迭代a=2b-1,這樣,迭代后,r=b-1。如果a小于2N,這樣大約需要4N次迭代。而考慮Stein算法,每次迭代后,顯然A(n+1)B(n+1)≤AnBn/2,最大迭代次數(shù)也不超過4N次。也就是說,迭代次數(shù)幾乎是相等的。但是,需要注意的是,對于大素數(shù),試商法將使每次迭代都更復雜,因此對于大素數(shù)Stein將更有優(yōu)勢。