辗转相除法也叫欧几里得算法（Euclidean Algorithm），用于求两个正整数的最大公约数，最大公约数，也叫gcd, 是其英文名greatest common divisor的简写。1.辗转相除法求最大公约数的原理对于两个整数a和b，假设其最大公约数是d。那么a能被d整除，b也能被d整除，那么a mod b也能被d整除。也就是说，a和b的最大公约数与b和a mod b的最大公约数相同。如下公式所示。gcd(a, b)=gcd(b, a mod b)可以反复套用以上公式，直到a mod b为0为止，如下图公式所示。gcd(a, 0) = a此时a的值即为a和b的最大公约数。例如，求48和18的最大公约数，如下所示。gcd(48, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0)