引言

欧几里得算法用于求两整数的最大公约数，是一个简单却经典的算法，很多算法或者数论领域的入门书都将它作为引子。

描述

已知整数，令，然后由下式

依次计算，直到某余数，此时最后的非零余数就是。

证明

将欧几里得算法的递归式展开，如下：

首先证明是的公因数。从展开的方程组从下向上分析，最后一行表明。倒数第二行表明。依此类推，可得。
然后证明是的最大公因数。设是的任意公约数。从展开的方程组从上向下分析，第一行等价于，由，得。第二行等价于，由，得。依此类推直到倒数第二行，可得。，故就是的最大值，因此，欧几里得算法得证。
欧几里得算法的收敛性是不证自明的，显然等余数组成的数列单调递减，该数列的最小值是。