欧几里得算法，也称为辗转相除法，是一种用于计算两个非负整数最大公约数（GCD）的算法。这种算法的名字来源于古希腊数学家欧几里得，他在其著作《几何原本》中首次描述了这种方法。欧几里得算法是通过连续除法运算，每次用较小的数除以较大的数，然后再用余数继续除以较小的数，如此反复，直到余数为零，最后的除数即为两数的最大公约数。
(a,b)=(q1b+r1,b)=(r1,b)=(r1,q2r1+r2)=(r1,r2)=…=(rn−2,rn−1)(a,b)=(q_1b+r_1,b) =(r_1,b)=(r_1,q_2r_1+r_2) =(r_1,r_2) =\ldots=(r_{n-2},r_{n-1})