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