維基百科:優良條目/輾轉相除法

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