公約数は最大公約数の約数の証明について

整数 $a, b$ の任意の公約数 $d$ は, $a, b$ の最大公約数 $g$ の約数である.

よくある証明は

$$
a x + b y = g
$$

となる $x, y$ が存在するから, $d$ が $a, b$ の公約数であることより左辺は $d$ で割り切れ,右辺も $d$ で割り切れる,というもの.全然構わないんですけど, $a x + b y = g$ を満たす $x, y$ が存在するっていう性質は少しばかり贅沢だなと思うわけです(専門っぽく聞こえる用語を使えば整数環 $\mathbf{Z}$ は単項イデアル整域だから〜).公約数は最大公約数の約数だなんて,なんとなく明らかなことを証明するのに,このような贅沢な方法でなければ証明できないのかと考えました.で,調べてみると,もっと初等的な証明があったので説明します(参考:河田直樹『高校・大学生のための整数の理論と演習』(現代数学社)).

そのためには

整数 $a, b$ の任意の公倍数 $m$ は, $a, b$ の最小公倍数 $l$ の倍数である.

を用います.こちらは,除法の原理より簡単に示せます.実際, $m$ を $l$ で割ったときの商を $q$,余りを $r$ とすると
$$
m = l q + r\quad(0\leqq r < l)
$$
が成り立ちます. $r \neq 0$ を仮定すると
$$
r = m – l q
$$
において, $m, l$ は $a, b$ の倍数ですから, $r$ は $l$ より小さい $a, b$ の公倍数となり, $l$ の最小性に矛盾します.よって $r = 0$ です.つまり, $m$ は $l$ で割り切れるから, $l$ の倍数ということです.

さて,本題の証明に入ります. $d, g$ の最小公倍数が $g$ であることを示せば, $g$ は $d$ の倍数,すなわち, $d$ は $g$ の約数がいえて証明は完了します.ひとまず $d, g$ の最小公倍数を $l$ とすると,公倍数の定義より $g\leqq l$ です.あとは, $l\leqq g$ を示せばおしまいです.ここで, $d \mid a$ かつ $g\mid a$ より, $a$ は $d, g$ の公倍数.公倍数は最小公倍数の倍数だから, $l \mid a$.同様にして $l \mid b$.故に, $l$ は $a, b$ の公約数. $g$ の最大性より $l\leqq g$ が成り立ちます.以上で題意は示されました.

「公約数は最大公約数の約数の証明について」への2件のフィードバック

  1. 「公倍数の定義より g≦l です.あとは,l≧g を示せばおしまいです」のところ、不等号の向きが同じになっています。

    返信

コメントする