問題
3つの正の整数 の最大公約数が であるとき,次の問いに答えよ。
(1) の最大公約数は であることを示せ。
(2) の最大公約数となるような正の整数をすべて求めよ。
方針
(1)は共通素因数 が存在すると仮定し, を割ることから の少なくとも1つを割る。和と2次対称式の条件を合わせて,結局 が3数すべてを割る矛盾を導く。(2)は ,, とおき, と の恒等式から共通約数 が と を割ることを示す。(1)を使って素因数を に限り,指数も1以下に抑える。最後に が実現する例を挙げる。
解答
(1)
が共通の素因数 をもつと仮定する。 は を割るので, の少なくとも1つを割る。対称性により が を割るとしてよい。
このとき は を割るから, を割る。また は を割り,かつ を割るので, を割る。したがって は の少なくとも一方を割る。もし が を割れば, も割るので を割る。もし が を割っても同様に を割る。よって は すべてを割る。これは の最大公約数が であることに反する。したがって共通素因数は存在せず,最大公約数は である。
(2)
,, とおく。また を の最大公約数とする。 であり, は と を割るから, は を割る。また であり, は と を割るから, は を割る。
(1)より の最大公約数は である。したがって, の素因数 が 以外なら, は をすべて割ることになり矛盾する。よって の素因数は または に限られる。
さらに が を割ると仮定する。,, だから, は をすべて割る。これは (1) に反する。よって は で割り切れない。同様に が を割ると仮定すると, は をすべて割るので矛盾する。よって は で割り切れない。
したがって は のいずれかである。実際, では , では , では , では となる。ゆえに求める正の整数は である。