輾轉相除法
維基百科,自由的 encyclopedia
在數學中,輾轉相除法,又稱歐幾里得算法(英語:Euclidean algorithm),是求最大公約數的算法。輾轉相除法首次出現於歐幾里得的《幾何原本》(第VII卷,命題i和ii)中,而在中國則可以追溯至東漢出現的《九章算術》。
兩個整數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理:兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。例如,欲求252和105的最大公約數();因為,所以這個最大公約數也是42與105的最大公約數()。在這個過程中,較大的數縮小了,所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數為零。這時,所剩下的還沒有變成零的數就是兩數的最大公約數。由輾轉相除法也可以推出,兩數的最大公約數可以用兩數的整數倍相加來表示,如。這個重要的結論叫做貝祖定理。
輾轉相除法最早出現在歐幾里得的《幾何原本》中(大約公元前300年),所以它是現行的算法中歷史最悠久的。這個算法原先只用來處理自然數和幾何長度(相當於正實數),但在19世紀,輾轉相除法被推廣至其他類型的數學物件,如高斯整數和一元多項式。由此,引申出歐幾里得整環等等的一些現代抽象代數概念。後來,輾轉相除法又擴展至其他數學領域,如紐結理論和多元多項式。
輾轉相除法有很多應用,它甚至可以用來生成全世界不同文化中的傳統音樂節奏。[1]在現代密碼學方面,它是RSA算法(一種在電子商務中廣泛使用的公鑰加密算法)的重要部分。它還被用來解丟番圖方程,比如尋找滿足中國剩餘定理的數,或者求有限域中元素的逆。輾轉相除法還可以用來構造連分數,在施圖姆定理和一些整數分解算法中也有應用。輾轉相除法是現代數論中的基本工具。
輾轉相除法處理大數時非常高效,如果用除法而不是減法實現,它需要的步驟不會超過較小數的位數(十進制下)的五倍。拉梅於1844年證明了這點,同時這也標誌著計算複雜性理論的開端。