問題はこちら(画像をクリックするとPDFファイルで開きます。)
第3問もシンプルな題意です。
3つの整数の最大公約数をいきなり扱おうとしても中々難しいものがあると思います。
ひとまず2つの最大公約数を考えようとするのが自然でしょう。
そこで、n^{2}+2 と n^{4}+2 の最大公約数 G_{n} について考えてみます。
n^{4}+2=(n^{2}-2)(n^{2}+2)+6
ですから、ユークリッドの互除法により
- G_{n} は n^{2}+2 と 6 の最大公約数
ということになります。
G_{n} は n を 6 で割った余りで分類することで求めることができます。
問題は G_{n} が残る n^{6}+2 を割り切るかどうかという問題です。
ただ、これについても G_{n} が分かっていれば、確認作業程度の労力で事足ります。
幸いにも今回は各場合分けにおけるどの場合でも G_{n} は n^{6}+2 を割り切りますから、
A_{n}=G_{n}
ということになります。
3数の最大公約数と、その中の2数の最大公約数について
一般的に、3つの整数 P , Q , R の最大公約数を g , その中の2数 P , Q の最大公約数を G とすると
g \leq G
ということになります。
2つ目までは共通で割り切れても、3つ目が割り切れず足を引っ張って最大公約数が小さくなってしまうかもしれないよね、というイメージです。
当初、この問題を見たときにこのイメージではさんで絞り込んでやっていくのかなとか、色々思うところがありましたが、やっていくうちに
そんなことするまでもなかった
という感じで終わってしまいました。