联系最大公约数与最小公倍数的乘积恒等式

第一步。对所有质数 $p$ 写出 $a$ 和 $b$ 的质因数分解:$a=\prod_p p^{e_p}$,$b=\prod_p p^{f_p}$,其中 $e_p,f_p\ge0$ 且只有有限个指数非零。

第二步。正整数 $d=\prod_p p^{c_p}$ 同时整除 $a$ 和 $b$,当且仅当对每个 $p$ 有 $c_p\le e_p$ 且 $c_p\le f_p$,故最大公因数取 $c_p=\min(e_p,f_p)$:$\gcd(a,b)=\prod_p p^{\min(e_p,f_p)}$。对公倍数做对偶推理,取同时不小于两者的最小指数,得 $\operatorname{lcm}(a,b)=\prod_p p^{\max(e_p,f_p)}$。

第三步。对任意两个实数都有 $\min(e_p,f_p)+\max(e_p,f_p)=e_p+f_p$。因此将两个乘积按质数逐项相乘,即得 $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=\prod_p p^{\min(e_p,f_p)+\max(e_p,f_p)}=\prod_p p^{e_p+f_p}=\left(\prod_p p^{e_p}\right)\left(\prod_p p^{f_p}\right)=ab$。