202606252211最小公倍数

最小公倍数

什么是最小公倍数？

对于 $a,b\in Z$，若有 $p\in Z$ 使得 $a|p$ 且 $b|p$，则称 $p$ 是 $a,b$ 的公倍数。公倍数不止一个，其中最小的称为最小公倍数，记作 $\text{lcm(a, b)}$. 用数学语言描述就是

$$\text{lcm}(a,b)=\min (\{p|a|p,b|p\}).$$

如何求解最小公倍数？

引理

若 $a,b$ 互质，则 $\text{lcm}(a,b)=|ab|$.

Theorem

$\text{gcd}(a,b)\cdot \text{lcm}(a,b)=|ab|$

简要证明：

设 $d=\text{gcd}(a,b)$，则有 $a=d{a}_1,b=d{b}_1$，且 $a_1,b_1$ 互质。若非如此，$a_1,b_1$ 中还能提取公约数放到 $d$ 中，这与 $d$ 是最大公约数矛盾。因此 $\text{lcm}(a_1,b_1)=a_1{b}_1$，再把 $d$ 乘回来得 $\text{lcm}(a,b)=d{a}_1{b}_1$. 于是，

$$\begin{array}{c}\text{gcd}(a,b)\cdot \text{lcm}(a,b)=d\cdot d{a}_1{b}_1=(d{a}_1)(d{b}_1)=ab.\end{array}$$

考虑到 gcd 和 lcm 通常取正职，而 $a,b$ 可能为负，所以加上绝对值。

有了上面的结论，我们只要求得 $a,b$ 的最大公约数，即可得到，

$$\text{lcm}(a,b)=\frac{|ab|}{\text{gcd}(a,b)}.$$

算法实现

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
    
def lcm(a, b):
    return a * b / gcd(a, b)

References

• 最小公倍数 - 维基百科