【整数問題】Indonesia MO 2023-5 をゆる〜く解説する

このアカウントでは、気が向いた時にてきとーな問題の解説記事を書いています。
基本的に大学入試レベルの問題(主に整数問題)を解説しますので、数オリ未経験の方も是非読んでみてください！
また、間違った議論や誤植などがあればコメントなどでご指摘を頂けるとありがたいです。

問題

英語の問題文(Aopsより)

和訳するとこんな感じです。

$${a,b}$$を正整数とする。
$${gcd(a,b)+lcm(a,b)}$$が$${a+1}$$の倍数であり、$${a≧b}$$であるとき、$${b}$$が平方数であることを示せ。

$${gcd(a,b)}$$は$${a}$$と$${b}$$の最大公約数、$${lcm(a,b)}$$は$${a}$$と$${b}$$の最小公倍数を表しています。(JMOでもある程度難易度の高い問題になると普通に問題文で使われることがあるので、覚えておくとよいでしょう。)

コメント

比較的シンプルな主張の整数問題です。
どうやって使うのか予想しづらい条件が並んでいて、かなりとっつきにくくなっていますね…

解説

全体の見通しがすぐにはたたないので、とりあえず条件を分かりやすく言い換えていきます。

まず、$${gcd(a,b)=g}$$、$${a=gx}$$、$${b=gy}$$とします。($${x,y}$$は互いに素な正整数)
$${lcm(a,b)=\frac{ab}{g}=gxy}$$ より、
$${gcd(a,b)+lcm(a,b)=g+gxy=g(xy+1)}$$
よって、$${g(xy+1)}$$は$${a+1}$$の倍数…①
また、$${a}$$と$${a+1}$$は互いに素なので、$${g}$$と$${a+1}$$は互いに素だと分かります。
よって①より、$${xy+1}$$は$${a+1}$$の倍数、つまり$${xg+1}$$の倍数だと分かります。

さて、これ以上進めるのは無理そうに見えます。(僕はここで一旦止まりました)
では、まずどういう場合であれば$${xy+1}$$が$${xg+1}$$の倍数になるかを考えてみます。
とりあえず、$${xy+1=xg+1}$$なら$${xy+1}$$は$${xg+1}$$の倍数になっていますね。
この時、$${x(y-g)=0}$$より、$${y=g}$$となります。
そしてここから$${b=g^2}$$が分かりますが…これ、平方数ですよね？
この問題のゴールである、「$${b}$$は平方数」というワードが登場したわけですから、とりあえずこの流れで$${xy+1=xg+1}$$かどうかで場合分けして考えてみましょう。
常に$${b=g^2}$$になる、とかであればありがたいのですが…

とりあえず、$${xy+1=k(xg+1)}$$と置きます。($${k}$$は正整数)
[1] $${k=1}$$の時
先程述べた通り、$${b=g^2}$$なので、$${b}$$は平方数です。
[2]$${k≧2}$$の時
$${xy+1=k(xg+1)}$$を整理して、$${xy=kxg+(k-1)}$$
移項して、$${x(y-kg)=k-1}$$
ここから、$${k-1}$$は$${a}$$の倍数と分かります。
また、$${k≧2}$$より$${k-1≧1}$$なので、
$${k-1≧a}$$,つまり$${k≧a+1=xg+1}$$
これと$${xy+1=k(xg+1)}$$より、
$${xy+1=k(xg+1)≧(xg+1)^2=x(xg^2+2g)+1}$$となるので、
$${xy+1≧x(xg^2+2g)+1}$$
よって $${y≧xg^2+2g>x}$$
しかし、これは$${a≧b}$$より$${x≧y}$$であることに矛盾します。
よって$${k≧2}$$の場合条件を満たす$${a,b}$$は存在しないとわかりました。
[1]、[2]より、$${b}$$は平方数だと分かります。(証明終)