輾轉相除法 在數學中辗转相除法又称欧几里得算法英語Euclidean algorithm是求最大公约数的算法辗转相除法首次出现于欧几里得的几何原本第VII卷命题i和ii中而在中国则可以追溯至东汉出现的九章算术 两个整数的最大公约数是能够同时整除它们的最大的正整数辗转相除法基于如下原理两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数例如欲求和的最大公约数            displaystyle times times  因为      displaystyle div  所以这个最大公约数也是与的最大公约数      displaystyle times  在这个过程中较大的数缩小了所以继续进行同样的计算可以不断缩小这两个数直至余数为零这时所剩下的还没有变成零的数就是两数的最大公约数由辗转相除法也可以推出两数的最大公约数可以用两数的整数倍相加来表示如             displaystyle times times  这个重要的結論叫做貝祖定理 辗转相除法最早出现在欧几里得的几何原本中大约公元前年所以它是现行的算法中歷史最悠久的这个算法原先只用来处理自然数和几何长度相當於正實數但在世纪辗转相除法被推广至其他类型的數學物件如高斯整数和一元多项式由此引申出欧几里得整环等等的一些现代抽象代数概念后来辗转相除法又扩展至其他数学领域如纽结理论和多元多项式 辗转相除法有很多应用它甚至可以用来生成全世界不同文化中的传统音乐节奏在现代密码学方面它是RSA算法一种在电子商务中广泛使用的公钥加密算法的重要部分它还被用来解丢番图方程比如寻找满足中国剩余定理的数或者求有限域中元素的逆辗转相除法还可以用来构造连分数在施图姆定理和一些整数分解算法中也有应用辗转相除法是现代数论中的基本工具 辗转相除法处理大数时非常高效如果用除法而不是减法实现它需要的步骤不会超过较小数的位数十进制下的五倍拉梅于年证明了这点同時這也標誌著计算复杂性理论的開端