公約数と最大公約数 - You / がらくた数学

　ふたつの自然数 \(a,\ b\) の最大公約数を \(g\) とすると、 \(a,\ b\) の公約数は \(g\) の約数になっており、 \(g\) の約数は \(a,\ b\) の公約数になっている。

　これ、中学校あたりで自明であるかのように教えられます。「 \(g\) の約数は \(a,\ b\) の公約数になっている」の方はほぼ自明でいいと思いますが、「\(a,\ b\) の公約数は \(g\) の約数になっている」の方は実際に証明しようとすると意外と面倒です。拡張ユークリッドの互除法などの帰結として得られる、不定方程式の解の存在から証明するとあっという間に終わるのですが、いささか大げさすぎる気がします。同様に思う人は結構いるらしく、例えば公約数は最大公約数の約数の証明について（My Extra Dimension）では、ある2数の公倍数は、最小公倍数の倍数である、という事実を使って証明する方法が載っています。

　これもメジャーな方法のようなのですが、公約数の証明に公倍数を駆り出す必要があるのがちょっと気に入らないので、もうひとつ方法を考えてみました。スマートとは言いがたいですが。もし間違ってたら恥ずかしいので黙って消す（笑）。

　まず、最大公約数は \(a,\ b\) の約数なので、適当な自然数 \(q_{ag},\ q_{bg}\) を使ってこう書けます。

\begin{align} a &= q_{ag} \cdot g \label{eqn-ag-div} \\ b &= q_{bg} \cdot g \label{eqn-bg-div} \end{align}

　ここで、 \(a,\ b\) の約数で、 \(g\) の約数ではない \(d\) を考えます。 \(d\) は \(g\) の約数ではないので \(g\) を割り切ることはできませんし、1でもありません。また、\(g\) は \(a,\ b\) の約数のうち最大のものなので \(d\) は \(g\) よりも小さいはずです。つまり、 \(d\) は1より大きく、 \(g\) より小さい整数です。したがって、 \(g\) を \(d\) で割ると商は必ず1以上で、あまりは0になりません。つまり、こう書けます。

\begin{align*} g &= q_{gd} \cdot d + r_{gd} \hspace{1em} (0 < q_{gd},\ 0 < r_{gd} < d) \end{align*}

　これをさっきの式（\ref{eqn-ag-div}）・式（\ref{eqn-bg-div}）にぶち込みます。

\begin{align*} a &= q_{ag} \cdot (q_{gd} \cdot d + r_{gd}) \\ &= q_{ag} \cdot q_{gd} \cdot d + q_{ag} \cdot r_{gd} \\ b &= q_{bg} \cdot (q_{gd} \cdot d + r_{gd}) \\ &= q_{bg} \cdot q_{gd} \cdot d + q_{bg} \cdot r_{gd} \end{align*}

\(d\) は \(a,\ b\) を割り切るので、この式の右辺も \(d\) で割り切れなければなりません。第1項は \(d\) で割り切れるので、第2項も \(d\) で割り切れる必要があります。つまり、やっぱり適当な自然数を持ってきてこう書けるはずです。

\begin{align*} q_{ag} \cdot r_{gd} &= q_{ad} \cdot d \\ q_{ag} &= q_{ad} \cdot d / r_{gd} \\ q_{bg} \cdot r_{gd} &= q_{bd} \cdot d \\ q_{bg} &= q_{bd} \cdot d / r_{gd} \end{align*}

　これを式（\ref{eqn-ag-div}）・式（\ref{eqn-bg-div}）に突っ込むと、

\begin{align*} a &= q_{ag} \cdot g \tag{\ref{eqn-ag-div}} \\ &= ( q_{ad} \cdot d / r_{gd} ) \cdot g \\ &= q_{ad} \cdot (d / r_{gd} ) \cdot g \\ b &= q_{bg} \cdot g \tag{\ref{eqn-bg-div}} \\ &= (q_{bd} \cdot d / r_{gd}) \cdot g \\ &= q_{bd} \cdot (d / r_{gd}) \cdot g \end{align*}

となります。この式は \((d / r_{gd}) \cdot g\) が \(a,\ b\) の公約数だということを示しています。ところが、先ほど説明したように \(0 < r_{gd} < d\) なので \(d / r_{gd} > 1\) です。ということは \((d / r_{gd}) \cdot g > g\) です。しかし、 \(g\) は \(a,\ b\) の最大公約数なので、 \(g\) よりも大きい公約数は存在しません。つまり、このような \(d\) は存在しません。

　よって、 \(a,\ b\) の公約数であり、 \(g\) の約数になっていないものは存在しません。 \(a,\ b\) の公約数ならば必ず \(g\) の約数になっています。

home / junkbox / math / gcd 公約数と最大公約数