引言

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

描述

已知整数 $a,b$ ，令 $r_{-1}=a, r_0=b$ ，然后由下式
$r_{i-1}=q_{i+1}*r_{i}+r_{i+1}, i \in \mathbb{N+}$
依次计算 $r_{i+1}$ ，直到某余数 $r_{n+1}=0$ ，此时最后的非零余数 $r_{n}$ 就是 $gcd(a,b)$ 。

证明

将欧几里得算法的递归式展开，如下：
$\begin{split} \begin{array}{c} a = q_1 * b + r_1 \\ b = q_2 * r_1 + r_2\\ r_1 = q_3*r_2 + r_3 \\ r_2 = q_4*r_3 + r_4 \\ \vdots\\ r_{n-3} = q_{n-1}*r_{n-2} + r_{n-1}\\ r_{n-2} = q_{n}*r_{n-1} + r_{n}\\ r_{n-1} = q_{n+1} * r_{n} + 0 \end{array} \end{split}$
首先证明 $r_n$ 是 $a,b$ 的公因数。从展开的方程组从下向上分析，最后一行表明 $r_n|r_{n-1}$ 。倒数第二行表明 $r_n|r_{n-2}$ 。依此类推，可得 $r_n|r_2,r_1,b,a$ 。
然后证明 $r_n$ 是 $a,b$ 的最大公因数。设 $m$ 是 $a,b$ 的任意公约数。从展开的方程组从上向下分析，第一行等价于 $r_1=a-q_1*b$ ，由 $m|a,b$ ，得 $m|r_1$ 。第二行等价于 $r_2=b-q_2*r_1$ ，由 $m|r_1,b$ ，得 $m|r_2$ 。依此类推直到倒数第二行，可得 $m|r_n$ 。 $m|r_n \to m \leq r_n$ ，故 $r_n$ 就是 $m$ 的最大值，因此 $m=gcd(a,b)$ ，欧几里得算法得证。
欧几里得算法的收敛性是不证自明的，显然 $r_2,r_2,r_3$ 等余数组成的数列单调递减，该数列的最小值是 $0$ 。