2015/02/24

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

分野: 整数問題  レベル: 基本公式

最大公約数と最小公倍数の関係:
正の整数 $a,b$ に対して,それらの最大公約数を $g$,最小公倍数を $l$ とおくと $ab=gl$
(最大公約数と最小公倍数の積がもとの二つの数の積に等しい)


覚える必要はありませんが,シンプルで美しい定理です。二通りの証明を解説します。

具体例

証明の前に実験してみましょう。まずは数字が小さい例です。
・ $a=12,b=18$ のとき,
$a=2^2\times 3$
$b=2\times 3^2$
より,最大公約数は $g=6$,最小公倍数は $l=2^2\times 3^2=36$ です。
実際,$ab=216=gl$ となっています!


もう少し数字が大きい場合の例です!
・ $a=72,b=182$ のとき,
$a=2^3\times 3^2$
$b=2 \times 7\times 13$
より,最大公約数は $g=2$,最小公倍数は $l=2^3\times 3^2\times 7\times 13=6552$ です。実際,$ab=13104=gl$ となっています。

素因数分解を用いた証明

具体例での実験を繰り返していると思いつきやすいであろう証明を解説します。記号がいろいろ登場して少し難しそうですが,考え方は難しくありません。

なお,$\max(e_i,f_i)$ は $e_i$ と $f_i$ のうち大きい方,$\min(e_i,f_i)$ は小さい方を表します。

証明

$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$ となる)。

このとき,

  • 最大公約数 $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$ が示された。

$\min(e_i,f_i)+\max(e_i,f_i)=e_i+f_i$ が成立するのが証明の核心部分です。

最大公約数と最小公倍数の定義を考えた証明

もう一つ証明方法を解説します!

証明

$g$ が $a$ と $b$ の最大公約数なので,互いに素な整数 $a’,b’$を使って
$a=ga’,b=gb’$と書ける。

このとき「補題:$a$ と $b$ の最小公倍数は $l=ga’b’$である」
より,$gl=g(ga’b’)=ga’gb’=ab$ となり題意は証明された。

補題の証明:
最小公倍数は $a=ga’$の倍数なので,整数 $n$ を用いて $l=nga’$と書ける。これが $b=gb’$の倍数となるのは「 $na’$が $b’$の倍数となる」のは条件。ところが,$a’$と $b’$は互いに素なので,先ほどの条件は「 $n$ が $b’$の倍数となるとき」と言い換えられる。よって,最小公倍数は $n=b’$のときに対応して,$l=ga’b’$となる。

僕は一つ目の証明の方が好きです!

Tag: 数学Aの教科書に載っている公式の解説一覧

分野: 整数問題  レベル: 基本公式