亦称“欧几里得算法”。求两个正整数的最大公约数的方法。以112和77两数为例（如右式）：在式中用77除112得余数35，再用35除77得余数7，再用7除35，余数为零。这样，最后的除数7是112和77的最大公约数。求两个多项式的最高公因式也可用这个方法。