在數(shù)學(xué)中,輾轉(zhuǎn)相除法,又稱歐幾里得算法,是求最大公約數(shù)的算法.輾轉(zhuǎn)相除法首次出現(xiàn)于歐幾里得的《幾何原本》（第VII卷,命題i和ii）中,而在中國(guó)則可以追溯至東漢出現(xiàn)的《九章算術(shù)》.兩個(gè)整數(shù)的最大公約數(shù)是能夠同時(shí)整除它們的最大的正整數(shù).輾轉(zhuǎn)相除法基于如下原理：兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的差的最大公約數(shù).例如,252和105的最大公約數(shù)是21（252 = 21 × 12；105 = 21 × 5）；因?yàn)?52 − 105 = 147,所以147和105的最大公約數(shù)也是21.在這個(gè)過(guò)程中,較大的數(shù)縮小了,所以繼續(xù)進(jìn)行同樣的計(jì)算可以不斷縮小這兩個(gè)數(shù)直至其中一個(gè)變成零.這時(shí),所剩下的還沒有變成零的數(shù)就是兩數(shù)的最大公約數(shù).由輾轉(zhuǎn)相除法也可以推出,兩數(shù)的最大公約數(shù)可以用兩數(shù)的整數(shù)倍相加來(lái)表示,如21 = 5 × 105 + (−2) × 252.這個(gè)重要的等式叫做貝祖等式.輾轉(zhuǎn)相除法最早出現(xiàn)在歐幾里得的幾何原本中（大約公元前300年）,所以它是現(xiàn)在仍在使用的算法中最早出現(xiàn)的.這個(gè)算法原先只用來(lái)處理自然數(shù),但在19世紀(jì),輾轉(zhuǎn)相除法被推廣至其他類型的數(shù),如高斯整數(shù)和一元多項(xiàng)式.自此,現(xiàn)代抽象代數(shù)概念如歐幾里得整環(huán)開始出現(xiàn).后來(lái),輾轉(zhuǎn)相除法又?jǐn)U展至其他數(shù)學(xué)領(lǐng)域,如紐結(jié)理論和多元多項(xiàng)式.輾轉(zhuǎn)相除法有很多應(yīng)用,它甚至可以用來(lái)生成全世界不同文化中的傳統(tǒng)音樂(lè)節(jié)奏.在現(xiàn)代密碼學(xué)方面,它是RSA算法（一種在電子商務(wù)中廣泛使用的公鑰加密算法）的重要部分.它還被用來(lái)解丟番圖方程,尋找滿足中國(guó)剩余定理的數(shù),或者求有限域的倒數(shù).輾轉(zhuǎn)相除法還可以用來(lái)構(gòu)造連分?jǐn)?shù),在施圖姆定理和一些整數(shù)分解算法中也有應(yīng)用.輾轉(zhuǎn)相除法是現(xiàn)代數(shù)論中的基本工具.輾轉(zhuǎn)相除法處理大數(shù)時(shí)非常高效,它需要的步驟不會(huì)超過(guò)較小數(shù)的位數(shù)（十進(jìn)制下）的五倍.加百利·拉梅(Gabriel Lamé)于1844年證明了這點(diǎn),開創(chuàng)了計(jì)算復(fù)雜性理論.