最大公约数 Greatest Common Divisor
两非负整数 $\scriptsize a$ 和 $\scriptsize b$ 的最大公约数记为 $\scriptsize d=gcd(a,b)$
int gcd(int a, int b) { return b == 0? a: gcd(b, a % b); }
证明
欲证 $\scriptsize gcd(a,b) = gcd(b, a\mod b)$
即证 $\scriptsize gcd(a,b)$ 和 $\scriptsize gcd(b, a\mod b)$ 互为因数
一、先证 $\scriptsize gcd(a,b)$ 是 $\scriptsize gcd(b, a\mod b)$ 因子
即证 $\scriptsize gcd(a,b)$ 是 $\scriptsize b$ 和 $\scriptsize a\mod b$ 的公因子
1）$\scriptsize gcd(a,b)$ 本身是 $\scriptsize b$ 的因子
2）此证 $\scriptsize gcd(a,b)$ 是 $\scriptsize a\mod b$ 的因子：$\scriptsize a\mod b = a – \lfloor a / b\rfloor b$ 为 $\scriptsize a$ 和 $\scriptsize b$ 的线性组合，而两数的公约数一定为两数线性组合的公约数，则 $\scriptsize gcd(a,b)$ 是 $\scriptsize a\mod b$ 的因子
二、再证 $\scriptsize gcd(b, a\mod b)$ 是 $\scriptsize gcd(a,b)$ 因子
即证 $\scriptsize gcd(b, a\mod b)$ 是 $\scriptsize a$ 和 $\scriptsize b$ 的公因子
1）$\scriptsize gcd(b, a\mod b)$ 本身是 $\scriptsize b$ 的因子
2）此证 $\scriptsize gcd(b, a\mod b)$ 是 $\scriptsize a$ 的因子：$\scriptsize a = \lfloor a / b\rfloor b + a\mod b$，则 $\scriptsize a$ 是 $\scriptsize b$ 和 $\scriptsize a \mod b$ 的线性组合，两数的公约数 $\scriptsize gcd(b, a\mod b)$ 一定为$\scriptsize b$ 和 $\scriptsize a \mod b$ 线性组合的公约数，得证
第二个参数单调递减，直至递归边界 $\scriptsize gcd(d,0) = d$
最小公倍数 Least Common Multiple
两非负整数 $\scriptsize a$ 和 $\scriptsize b$ 的最小公倍数记为 $\scriptsize lcm(a,b)$
int lcm(int a, int b) { return a / gcd(a, b) * b; }
说明
$\scriptsize a = gcd(a,b) * x$，$\scriptsize b = gcd(a,b) * y$
$\scriptsize x$ 和 $\scriptsize y$ 是 $\scriptsize a$ 和 $\scriptsize b$ 的最小互质因子，否则 $\scriptsize gcd(a,b)$ 未达到最大
$\scriptsize lcm(a,b) = x * y * gcd(a,b)$ 是同时包含这三个因子的最小乘积，即为最小公倍数
例码中先算除法再算乘法，利于避免乘法溢出
扩展欧几里得算法 Extend Euclid
扩展欧几里得算法用来计算二元一次方程 $\scriptsize ax + by = n$ 的整数解