2018年 日本数学オリンピック本選 第１問 解答例
黒板に$${1}$$以上$${100}$$以下の整数が１つずつ書かれている。黒板から整数$${a, b}$$を選んで消し、新たに$${a^2b^2+3}$$と$${a^2+b^2+2}$$の最大公約数を書くという操作を繰り返し行う。黒板に書かれている整数が１つだけになったとき、その整数は平方数ではないことを示せ。
考え方：
すこしややこしい操作をするのでとっかかりが難しいです。
色々実験をしてみながら、整数問題のセオリーである剰余・倍数に注目しましょう。
平方数が多く現れる場合、$${3}$$での剰余をまず考えるのが吉のようです。
なお、私は、新たに書かれる整数が
$${(a^2b^2 +3) - (a^2 +b^2+2) = (a^2 - 1)(b^2 -1)}$$
$${(a^2b^2 +3) + 3(a^2 +b^2+2) = (a^2 + 3)(b^2 +3)}$$
の公約数であることが使えないかと考えているうちに気づきました。
解答例：
$${a, b}$$の両方が$${3}$$の倍数のとき、$${a^2+b^2+2}$$は$${3}$$の倍数ではない。
$${a, b}$$の両方が$${3}$$の倍数ではないとき、$${a^2b^2+3}$$は$${3}$$の倍数ではない。
よっていずれの場合も新たに書かれる数は$${3}$$の倍数ではない。
$${a, b}$$の一方が$${3}$$の倍数で他方が$${3}$$の倍数ではないとき、
$${a^2b^2+3}$$と$${a^2+b^2+2}$$のいずれも$${3}$$の倍数になるので、
新たに書かれる数は$${3}$$の倍数となる。
よって、黒板に書かれている$${3}$$の倍数の個数は１回の操作で変化しないか２つ減るかのいずれかである。
初めに書かれている$${3}$$の倍数の個数は$${33}$$であるため、
最後に残る１つの整数は$${3}$$の倍数になる。
一方、$${a^2b^2+3}$$は$${9}$$の倍数になることはないため、
最後に残る整数は$${9}$$の倍数になりえない。
よってこれは平方数ではない。
お知らせ：
少しでも興味深い、楽しいと感じたらぜひスキやコメント、フォローください！
間違いなど見つけましたら是非お教えください。
他に公開している記事などの一覧はこちら
ぜひ初めに見てください。｜光捷 (note.com)