最小公倍数

对正整数 $a,b$，最小公倍数（least common multiple）是同时被两数整除的最小正整数，记作 $\mathrm{lcm}(a,b)$。例如 12 的倍数依次有 12、24、36，18 的倍数有 18、36，所以 $\mathrm{lcm}(12,18)=36$。

与最大公约数的乘积关系

若 $d=gcd(a,b)$，可写 $a=du,b=dv$，其中 $gcd(u,v)=1$。同时是 $a,b$ 倍数的正整数必须含有 $d$，并且其余部分要同时容纳互素的 $u,v$；最小者为 $duv$。因此 $$\mathrm{lcm}(a,b)=\frac{ab}{gcd(a,b)},gcd(a,b)\mathrm{lcm}(a,b)=ab.$$ 在 12 与 18 的例子里，$gcd(12,18)=6$，故 $12\cdot 18/6=36$。

也可逐个素数看指数。$12=2^2\cdot 3$、$18=2\cdot 3^2$；公约数取每个素数的较小指数 $2\cdot 3=6$，公倍数取较大指数 $2^2\cdot 3^2=36$。较大指数与较小指数相加，恰等于原两指数之和，因而得到乘积公式。

使用范围

公式在上述写法中假定 $a,b>0$。对含零的整数对，常约定 $\mathrm{lcm}(a,0)=0$（$a\ne 0$），但此时“最小正公倍数”这句定义不能照搬，因为零没有正倍数。先说明采用哪一种定义，才能避免把边界约定混进正整数证明。

参考资料

• MIT，Mathematics for Computer Science，Number Theory 章节。
• MIT 18.781，初等数论讲义。
• 继续阅读：最大公约数、算术基本定理。