简介
辗转相除法，又称欧几里得算法，用于系统性地求两个自然数的最大公约数。
核心思想
对于任意两个正整数 $a$ 和 $b$ ，求 $a$ 和 $b$ 的最大公约数 $gcd(a, b)$，等价于求解 $gcd(b, a \% b)$，相关资料一般会限定 $a \geq b$，但其实即使 $a < b$ 也无妨，在这种情况下，第一步计算相当于交换 $a$ 和 $b$ 的位置。
证明该算法所需知识
下文的论证会用到三种相关的数学方法，分别是数学归纳法、递归和无穷递降。
归纳
数学归纳法经常用来证明某个定理对所有自然数成立：首先证明定理对一个特定的数n0成立（通常是1）；然后证明如果定理对自然数n成立的话，那么它对自然数n + 1成立。这样，便可证明定理对所有大于n0的自然数也成立。
递归
递归是将相关的数组成一个数列$(a1, a2, a3…)$，当中除初始项外，其中每一项都用前一项或前几项表示。如斐波那契数列就是递归的，每一项$Fn$都等于$F{n−1} + F_{n−2}（n\geq2）$。辗转相除法中的一些等式也是递归的。
无穷递降
最后，无穷递降是用方程的一个自然数解导出比它小的自然数解。但是，这种转化不能永远进行下去，因为只有有限个小于原来的自然数解的自然数。所以，要么方程无解，不然在有限步内必然能得出最小的自然数解。在下文会用到此法来证明辗转相除法一定会在有限步内结束。
算法步骤
下面以非负整数为例说明如何算法步骤，每一次计算的输入都是前两次计算的非负余数 $r{k-1}$和$r{k-2}$，记$a=r{-2}$，$b=r{-1}$，按如下步骤递归计算
$a = p0b + r_0$
$b = p_0r_0 + r_1$
$r_0 = p_0r_1 + r_2$
$r_1 = p_0r_2 + r_3$
…
$r{k-2} = p0r{k-1} + r_k$
按照该算法进行计算，$r_k$必然会逐渐减小，并且由于$[0,r_0]$之间数字有限，该算法必然能够在第$N$步终止。
此时$rN$为0，$r{N-1}$即为$gcd(a,b)$
证明上述算法的正确性
辗转相除法的正确性可以分成两步来证明。在第一步，我们会证明算法的最终结果$r{N-1}$同时整除$a$和$b$。因为它是一个公约数，所以必然小于或者等于最大公约数$g$。在第二步，我们证明$g$能整除$r{N-1}$。所以g一定小于或等于$r{N-1}$。两个不等式只在$r{N-1}=g$时同时成立。具体证明如下：
(1) $r_{N-1}$能整除$a$和$b$
在算法终止时，余数$rN=0$。则有：$r{N-2} = p0r{N-1}$
说明$r{N-1}$能整除$r{N-2}$，又根据$r{N-3} = p_0r{N-2} + r{N-1}$
可推断$r{N-1}$能整除$r{N-3}$，以此类推，最终可推断：
**$r{N-1}$能整除$a$和$b$，说明 $r{N-1}$是$a$和$b$的一个公约数**，且由于$g$是最大公约数，应有$r{N-1} \leq g$
(2) $g$能整除$r_{N-1}$
根据定义，$g$是$a$和$b$的最大公约数，则$g$能整除$a$和$b$，$a$和$b$可表示为$a=mg$，$b=ng$
由$r0=a-p_0b=mg-p_0ng=(m-p_0n)g$，可知$g|r_0$，即$g$能整除$r_0$,
由$r_1=b-p_0r_0$，$g|r_0$，$g|b$，可得$g|r_1$,
依此类推，最终可得$g|r{N-1}$，则$g \leq r_{N-1}$
综合(1)(2)，可知$g=r_{N-1}$