欣赏代码 #
在深入学习之前，先来欣赏一下辗转相除法的优美代码：
int gcd(int a, int b){
return b == 0 ? a : gcd(b, a % b);
}这个算法太优美了，函数内仅仅一行，就可以计算出任意两个数的最大公因数，而且非常易于记忆。这也就成了大部分高校考察编程水平的一个试金石。
那么代价是什么？
显而易见的代码背后，往往隐藏着深邃的数学原理。
数学推导 #
定义 \(a\) , \(b\) 为待求公因数的一对整数，\(d\) 为其公因数（目前不一定是最大公因数，在计算中会逐步确认）。
我们可以引入两个参数 \(k\)、\(r\)，使得：
$$a = kb + r \tag{1}$$
显然，如果对 \(k\) 、\(r\) 不做限制的话，其取值有无限多个。为了便于在编程中使用int类型变量，于是在此规定一下 \(k\)、\(r\) 都得是整数，并且 \(k\) 得尽可能大。于是取值就唯一确定了。
既然唯一确定了，我们很自然地就想用 \(a\) 和 \(b\) 把 \(k\)、\(r\)表示出来，如你所见：
$$k=\lfloor \frac{a}{b} \rfloor \\ r=a\bmod b$$
或者用更习惯的C语言写法：k=a/b; r=a%b; (以上变量类型都是int)
所以你发现前面我废话了这么多其实就是为了引入两数相除的商k和余数r
为了便于书写，我这里规定 \(\mid\) 符号为整除符号，比如 \(3\mid12\) 表示12可以被3整除; \(7\mid21\) 表示21可以被7整除。其实不是我擅自规定的，数学家也这么用。
根据定义：
$$d \mid a \\ d \mid b \Rightarrow d \mid kb$$根据式（1）：
$$d \mid kb+r$$不知道看到这里有没有发现一点端倪。中学里面应该了解过，如果一个数能被整除，那么加上另一个能被整除的数，两数的和也是能被整除的。
所以可以推导出：
$$d \mid r$$我们把三个并在一起看:
$$d\mid a \\ d \mid b \\ d \mid r$$把b、r当成新的待求公因数的一对整数，可以继续推导得出：
$$d\mid b \\ d \mid r \\ d \mid b \bmod r$$所以这个公式就很显然了：
$$\gcd(a,b)=\gcd(b,a\bmod b)$$在程序中，这个递归会一直运行，直到 \( a \bmod b = 0\) 的时候，递归终止，返回最后的 \(d\) 。那么问题来了，为什么最后的 \(d\) 就是最大公因数，而不是其他随便一个公因数呢？
为什么是最大公因数？ #
假设辗转相除法进行到最后一步（\(a'\)、\(b'\) 都是上一次传递下来的值）：
$$a'=kb'+0$$也就是说：
$$a'=kb'$$根据整除的定义：
$$b' \mid a'$$很显然，\(a'\)、\(b'\) 的最大公因数就是 \(b'\) 本身。
接下来只要证明 \(a\)、\(b\) 和 \(a'\)、\(b'\) 的公因数的集合是一样的即可。
我们之前推导出：
$$\left.\begin{matrix} d \mid a \\ d\mid b \end{matrix} \right\} \Rightarrow d \mid r $$现在返回来推导：
$$\left.\begin{matrix} d \mid b \Rightarrow d \mid kb \\ d\mid r \end{matrix} \right\} \Rightarrow d \mid kb+r \Rightarrow d\mid a$$所以这两个互为充要条件：
$$d\mid a,\ d\mid b \iff d \mid b,\ d\mid r$$换句话说，在递归过程中，公因数的集合是不变的。不会扩充也不会缩减。
所以最后一步算出来的最大公因数 \(b'\) 就是整个的最大公因数！
图解 #
