最大公約数と最小公倍数の積の性質の２通りの証明

$a$ と $b$ の少なくともどちらか一方を割り切る素数を $p_1,p_2,\cdots ,p_k$ とおく。このとき，$a$ と $b$ を素因数分解すると，

$a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

$b=p_1^{f_1}p_2^{f_2}\cdots p_k^{f_k}$

となる（ただし，$e_i,f_i$ は $0$ 以上の整数であり，素因数分解に登場しない素数の部分の指数は $0$ となる）。

このとき，

• 最大公約数 $g$ を素因数分解したときの $p_i$ の指数は $\min(e_i,f_i)$
• 最小公倍数 $l$ を素因数分解したときの $p_i$ の指数は $\max(e_i,f_i)$

となる（※）。

よって，$gl$ を素因数分解したときの $p_i$ の指数は $\min(e_i,f_i)+\max(e_i,f_i)=e_i+f_i$

となり，$ab$ を素因数分解したときの $p_i$ の指数と等しい。

（$g,l$ には当然 $p_i$ 以外の素因数は登場しないので）$ab=gl$ が示された。

最小公倍数について考える。

$a$ は素因数 $p$ でちょうど $A$ 回割れ，$b$ は素因数 $p$ でちょうど $B$ 回割れるとする。

• $a$ と $b$ の公倍数は $p^A$ の倍数かつ $p^B$ の倍数なので，$p^A$ と $p^B$ の大きい方 $p^{\mathrm{max}(A,B)}$ の倍数である。
• 一方「最小」公倍数ならそれよりも多い回数 $p$ で割れるとおかしい。

つまり，$a$ と $b$ の最小公倍数は，$p$ でちょうど「$A$ と $B$ の大きい方」回だけ割れる。他の素因数も同様。

最大公約数も同様。

$g$ が $a$ と $b$ の最大公約数なので，互いに素な整数 $a',b'$ を使って

$a=ga',b=gb'$ と書ける。

このとき 「補題2：$a$ と $b$ の最小公倍数は $l=ga'b'$である」

より，$gl=g(ga'b')=ga'gb'=ab$ となり証明完了。