問題
とおく．
(1) は3以上の自然数で，ある自然数にたいしてはの倍数になっているとする．このときとのうち少なくとも一方はの倍数であることを示せ．
(2) 任意の自然数にたいしてがの倍数となるような自然数が存在することを示せ．
出典：京都大学 1998年度 前期日程 第2次学力試験 理系 第2問
方針
(1)では を展開し、 で割った後の偶奇を見る。 が の倍数で なら は奇数であるため、 が奇数の場合にはずらした方が1段高い の倍数になる。(2)は で まで出発し、(1)を使って割り切れる2の指数を帰納的に上げる。
解答
(1)
まず差を計算する。 である。 なので であり、 は の倍数である。
また、仮定より は の倍数であり、特に の倍数である。もし が偶数なら は奇数であり、8の倍数にはならない。したがって は奇数である。 とおく。 が偶数なら、 はすでに の倍数である。 が奇数の場合を考える。このとき だから、 で割って偶奇を見ると である。ここで なので は偶数であり、 と はともに奇数である。よって は偶数である。したがって は の倍数である。
以上より、 と のうち少なくとも一方は の倍数である。
(2)
とすると である。したがって については、 とすれば は の倍数である。
次に、ある について、 が の倍数となる自然数 が存在すると仮定する。(1)より、 と のどちらかを選べば、その値を として となる。しかも は自然数である。
したがって から始めてこの操作を繰り返すことで、任意の自然数 に対して、 が の倍数となる自然数 が存在する。