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

整数 \(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\geqq g\) を示せばおしまいです.ここで, \(d \mid a\) かつ \(g\mid a\) より,\(a\) は \(d, g\) の公倍数.公倍数は最小公倍数の倍数だから,\(l \mid a\).同様にして \(l \mid b\).故に,\(l\) は \(a, b\) の公約数.\(g\) の最大性より \(l\leqq g\) が成り立ちます.以上で題意は示されました.

コメントする