如果数 a 能被数 b 整除，a 就叫做 b 的倍数，b 就叫做 a 的约数。

几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。

几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数。

本文将使用欧几里德算法实现求两个数的最大公约数。

最大公约数与最小公倍数

最大公约数

欧几里德算法，也称辗转相除法

定理： gcd(a, b) = gcd(b, a mod b) ( a > b 且 a mod b 不为 0 ) 即 a 和 b 的最大公约数等于 b 和 a % b 的最大公约数

证明：a 可以表示成 a = kb + r，则 r = a mod b

假设 x 是 a, b 的一个公约数，则有 x|a , x|b , 而 r = a - kb，因此 x|r 因此 x 也是（ b, a mod b ）的公约数 因此（ a, b ）和（ b, a mod b ）的公约数是一样的，其最大公约数也必然相等 得证：当 a % b 为 0 的时候, 则另一个数为最大公约数

int gcd(int a, int b) {
    //如果a<b, 交换a b
    if(a < b) int tmp = a, a = b, b = tmp;
    //如果b为0则结束循环, 返回0, 否则计算b与a%b的gcd
    return b == 0 ? a : gcd(b, a % b);
}

最小公倍数

假设求 x, y 的最小公倍数

公式： x * y = 最小公倍数 * 最大公约数