如果存在一个整数 $k$，使得 $a = kd$，则称 $d$ 整除 $a$，记做 $d \mid a$，称 $a$ 是 $d$ 的倍数，如果 $d > 0$，称 $d$ 是 $a$ 的约数。特别地，任何整数都整除 $0$。

一组数的公约数，是指同时是这组数中每一个数的约数的数。而最大公约数，则是指所有公约数里面最大的一个。

欧几里得算法（辗转相除法）

如果我们已知两个数 $a$ 和 $b$，如何求出二者的最大公约数呢？

不妨设 $a > b$

我们发现如果 $b$ 是 $a$ 的约数，那么 $b$ 就是二者的最大公约数。下面讨论不能整除的情况，即 $a = b \times q + r$ ，其中 $r < b$。

我们通过证明可以得到 $\gcd(a, b) = \gcd(b, a\mod b)$，过程如下：

设 $a = bk + c$，显然有 $c = a \mod b$，设 $d \mid a, \ d \mid b$，则 $c = a - bk,\ \frac{c}{d} = \frac{a}{d} - \frac{b}{d}k$，由右边的式子可知 $\frac{c}{d}$ 为整数，即 $d \mid c$ 所以对于 $a, b$ 的公约数，它也会是 $a \mod b$ 的公约数。

反过来证明

设 $d \mid b,\ d \mid (a \mod b)$，可得 $a = bk + a \mod b, \ \frac{a}{d} = \frac{a \mod b}{d} + \frac{b}{d}k$，由右边的式子可知 $\frac{c}{d}$ 为整数，即 $d \mid a$，所以 $b,\ a \mod b$ 的公约数也是 $a, \ b$ 的公约数。

既然两式公约数都是相同的，那么最大公约数也会相同。

所以得到式子 $\gcd(a, b) = \gcd(b, a\mod b)$

既然得到了 $\gcd(a, b) = \gcd(b, r)$，这里两个数的大小是不会增大的，那么我们也就得到了关于两个数的最大公约数的一个递归求法。

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