最小公倍数、最大公约数
最大公因数(GCD)
欧几里得算法（辗转相除法）
在证明辗转相除法的正确性之前，我们需要列出下面几个定理：
- 如果两数有一个公共因子 d，那么 d 一定是这两数相加/相减的结果的因子。jd + kd = (j+k)d
- 任意两个大于零的整数 a 和 b 满足 a\ge b，都可以写成 a = b * q + r，其中 q 和 r 是非负整数，q 称为 a 除 b 的商，r 称为余数。
- 上式可变形为 r = a - b * q，取 q 为最大值，易知 r<b
- 如果 r 不为 0，b*(q + 1) - a = b - r 可得，a 与 b 的公因子一定是 b*(q+1) 与 a 的公因子，也就是 b 与 r 的公因子。又有 r + b * (q + 1) = a + b，r 与 b 的公因子也一定是 a 与 b 的公因子。a 与 b 的公因子一定是 b 与 r 的公因子，b 与 r 的公因子一定是 a 与 b 的公因子，因此 \{x|x = a 与 b 的公因子\} = \{x|x = b 与 r 的公因子\}
- 如果 r 为 0，即 b 是 a 的因子，那么 a 和 b 的最大公因子就是 b。
因此，如果 r\ne 0，则有公式：
\text{gcd}(r, b) = \text{gcd}(b, a)
因此可以得到辗转相除的过程：
- r = a \% b
- r 如果等于零，输出 b
- 否则 a = b，b = r，回到第一步
例：
22 与 8 的最大公因数：
- 22 \% 8 = 6 \ne 0
- 8 \% 6 = 2 \ne 0
- 6 \% 2 = 0，输出 2
上面的过程对辗转相减法同样适用，边界条件是差为 0，输出减数。
更相减损法（二进制 GCD 算法）
是辗转相除/辗转相减的改进版，利用移位操作提高效率，适合计算机实现。
- 如果 a=0，返回 b，如果 b=0，返回 a。（边界条件：差为 0）
- 如果 a、b 都是偶数，返回 2*gcd(a/2, b/2)
- 如果 a 是偶数，返回 gcd(a/2,b)
- 如果 b 是偶数，返回 gcd(a,b/2)
- 如果都是奇数，a>b 则返回 gcd(a-b,b)，否则返回 gcd(a,b-a)
由于除 2 操作可以用移位实现，该算法通常比传统的辗转相除法快 20%~50%，而且适合超大数进行运算。
奇数 - 奇数必定是偶数，因此情况 5 一定不会连续出现，因此算法总体复杂度为 O(logN)。
最小公倍数(LCM)
用最大公因数求解
lcm 与 gcd 之间存在公式：
\mathrm{lcm}(a, b) = \frac{|a \times b|}{\mathrm{gcd}(a, b)}
要想证明这个公式，需要依赖整数的唯一质分解定理。
a = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k} \\
b = p_1^{f_1} \times p_2^{f_2} \times \dots \times p_k^{f_k}
其中 p_1,p_2... 为质数。a、b 的最大公因数其实就是：
\mathrm{gcd}(a, b) = p_1^{\min(e_1, f_1)} \times p_2^{\min(e_2, f_2)} \times \dots \times p_k^{\min(e_k, f_k)}
最小公倍数则是：
\mathrm{lcm}(a, b) = p_1^{\max(e_1, f_1)} \times p_2^{\max(e_2, f_2)} \times \dots \times p_k^{\max(e_k, f_k)}
然后，显然：
\max(e_i, f_i) + \min(e_i, f_i) = e_i + f_i
综合上面的表达式，得到：
a \times b = p_1^{e_1 + f_1} \times p_2^{e_2 + f_2} \times \dots \times p_k^{e_k + f_k}\\
= \mathrm{gcd}(a, b) \times \mathrm{lcm}(a, b)
求多个整数的 LCM
根据 LCM 的性质，可以得到：
\mathrm{LCM}(a_1, a_2, \dots, a_n) = \mathrm{LCM}(\mathrm{LCM}(a_1, a_2, \dots, a_{n-1}), a_n)