辗转相除法 又名欧几裏德算法（Euclidean algorithm），是求最大公约数的一种方法

• 用较大数除以较小数，再用出现的余数（第一余数）去除除数

• 再用出现的余数（第二余数）去除第一余数，

• 如此反复直到最后余数是0为止。

如果是求两个数的最大公约数那么最后的除数就是这两个数的最大公约数。

⒈ 令r为a/b所得余数（0≤r<b）若 r= 0算法结束；b 即为答案。
⒉ 互换：置 a←bb←r，并返回第一步

例如：求 1997 和 615 两个正整数的最大公约数，是这样进行的：