概述

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。

两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。【参考)】

流程

1. 假设要求 a 和 b 的最大公约数；
2. 首先取二者的模值 r = a % b;
3. 如果此时 r = 0 , 除数b 就是最大公约数；
4. 否则更新 a = b, b = r，然后循环；

原理

假设 a 和 b 的最大公约数为 m，那么 a = k1m ①, b = k2m ②。再假设 a > b，则 a = k3b + r ③。将 ①② 代入 ③，可以得到 k1m = k3*k2m + r，则 r = (k1 - k3*k2)m。也就是说余数 r 也有存在约数 m。则 m 也是 b 和余数 r 的一个公约数。

现在要证明 m 不仅是 b 和 r 的公约数，还是 b 和 r 的最大公约数。

我们还以 a 和 b 的最大公约数为 m为例，那么 a = k1m ①, b = k2m ②，可以得到的结论是 k1 和 k2 互质，也就是二者最大公约数为 1。我们可以通过反证法说明。

如果 k1 和 k2 不互质，那么势必存在一个公约数n，使得 k1 = i1n, k2 = i2n。则 a = k1m = i1nm. b = k2 = i2nm。那么 a 和 b 的最大公约数就是 nm 而不是 m，与条件 a 和 b 的最大公约数为 m矛盾，所以原命题成立。

因此如果k1和k2互质，m就是a和b的最大公约数。我们要证明 m 是 b 和 r 的最大公约数，就要说明 b = k2m 和 r = (k1-k3*k2)m 中的两个系数互质。

同样还是采用反证法。如果两个数不互质，k2 = j1n, (k1-k3*k2) = j2n，则 b = j1nm, c= j2nm, a = k3b + c = k3j1nm + j2nm = (k3j1 + j2)nm。a 和 b 的最大公约数就变成 nm 不是 m，与条件 a 和 b 的最大公约数为 m矛盾，所以原命题成立。

因此 b 和 r 的最大公约数也是 m。因此有 两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

然后我们再来看一种情况：r = 0 时 ，a = k3b ，最大公约数就为 b 本身。因此我们不断的用 b, r 更新 a, b 的终止条件就是 r = 0。

代码

定义中要求较大数除以较小数，然后取余数。为什么代码中没有去取小值的一步呢？

private int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}