维基百科:优良条目/辗转相除法

辗转相除法，又称欧几里得算法，在数学中是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》中，而在中国则可以追溯至东汉出现的《九章算术》。辗转相除法最早出现在欧几里得的几何原本中（大约公元前300年），所以它是现在仍在使用的算法中最早出现的。这个算法原先只用来处理自然数，但在19世纪，辗转相除法被推广至其他类型的数，如高斯整数和一元多项式。自此，现代抽象代数概念如欧几里得整环开始出现。后来，辗转相除法又扩展至其他数学领域，如纽结理论和多元多项式。辗转相除法有很多应用，它甚至可以用来生成全世界不同文化中的传统音乐节奏。在现代密码学方面，它是RSA算法（一种在电子商务中广泛使用的公钥加密算法）的重要部分。它还被用来解丢番图方程，寻找满足中国剩余定理的数，或者求有限域中元素的逆。辗转相除法还可以用来构造连分数，在施图姆定理和一些整数分解算法中也有应用。辗转相除法是现代数论中的基本工具。