維基百科:優良條目/輾轉相除法
外觀
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Euklid.jpg/110px-Euklid.jpg)
輾轉相除法,又稱歐幾里得算法,在數學中是求最大公約數的算法。輾轉相除法首次出現於歐幾里得的《幾何原本》中,而在中國則可以追溯至東漢出現的《九章算術》。輾轉相除法最早出現在歐幾里得的幾何原本中(大約公元前300年),所以它是現在仍在使用的算法中最早出現的。這個算法原先只用來處理自然數,但在19世紀,輾轉相除法被推廣至其他類型的數,如高斯整數和一元多項式。自此,現代抽象代數概念如歐幾里得整環開始出現。後來,輾轉相除法又擴展至其他數學領域,如紐結理論和多元多項式。輾轉相除法有很多應用,它甚至可以用來生成全世界不同文化中的傳統音樂節奏。在現代密碼學方面,它是RSA算法(一種在電子商務中廣泛使用的公鑰加密算法)的重要部分。它還被用來解丟番圖方程,尋找滿足中國剩餘定理的數,或者求有限域中元素的逆。輾轉相除法還可以用來構造連分數,在施圖姆定理和一些整數分解算法中也有應用。輾轉相除法是現代數論中的基本工具。