最大公约数和最小公倍数算法

因数分解

最大公约数

假定两个不全为 $0$ 的整数 $a$ 和 $b$ 的素因子分解为:
$$
a=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n} \\
b=p_1^{b_1}p_2^{b_2}\dots p_n^{b_n}
$$
每个整数都是非负整数,而且出现在 $a$ 和 $b$ 分解中的所有素数都包含在两个分解之中,必要时以 0 为指数出现。于是 $gcd(a, b)$ 由下面的公式给出
$$
gcd(a, b) = p_1^{min(a_1,b_1)}p_2^{min(a_2, b_2)}\dots p_n^{min(a_n,b_n)}
$$
例如,求 $120$ 和 $500$ 的最大公约数:
$$
120 = 2^3\cdot 3\cdot 5 , 500 = 2^2\cdot 5^3\\
gcd(120, 500) = 2^{min(3,2)}\cdot 3^{min(1,0)}\cdot 5^{min(1,3)}\\
= 2^3\cdot 3^0\cdot 5^1 = 20
$$

最小公倍数

因素分解也可以用来求最大公倍数,求 $a$ 和 $b$ 的最小公倍数的公式为:
$$lcm(a, b) = p_1^{max(a_1,b_1)}p_2^{max(a_2, b_2)}\dots p_n^{max(a_n,b_n)}$$

欧几里得算法

欧几里德算法又称辗转相除法,用于计算两个整数 a,b 的最大公约数。其计算原理依赖于下面的定理:
定理:$gcd(a,b) = gcd(b,a\;\mathbf{mod}\; b)$
证明:$a$ 可以表示成 $a = kb + r$,则 $r = a\;\mathbf{mod}\;b$
假设 $\;d$ 是 $a$,$b$ 的一个公约数,则有 $d\mid a$, $d\mid b$,而 $r= a - kb$,因此 $d\mid r$
因此 $\;d$ 是 $(b,a\;\mathbf{mod}\; b)$ 的公约数
假设 $\;d$ 是 $(b,a\;\mathbf{mod}\;b)$ 的公约数,则 $d\mid b$ ,$d\mid r$ ,但是 $a = kb +r$
因此 $\;d$ 也是 $(a,b)$ 的公约数