回到欧几里得算法。这个算法是通过推广以下的观察结果得到的，即对于两个数a〉b，可以通过连续的相减来找到最大公因数（highest common factor）。最大公因数也叫作最大公约数（greatest common divisor）。我们注意到r=a-b有一项性质：a，b，r中任意两者的公因数也是第三个数的因数。例如，如果c是a和b的公因数，于是a=ca1并且b=cb1，我们看到 r=a-b=ca1-cb1=c(a1-b1)，这就得出了r包含c的一个因数分解。于是，a和b的最大公因数等于b和r的最大公因数。因为这两个数都小于a，我们现在面对的是跟之前一样的问题，不过是相对于两个更小的数。重复应用这个方法，最终会得到一对数，它们的最大公因数可以一眼看出。（实际上，最后手中的两个数会变成相等的，因为如果不是这样，我们可以继续多做一步。这对数共同的值就是我们找的那个数。）
比如，要找a=558和b=396的最大公因数，第一次减法后我们得到r=558-396=162，因此新数对是396和162。由于396-162=234，所以我们的第三对数是234和162。随着我们继续下去，完整的数对依次是：