気になりすぎたので解いてみた。漫画内にヒントはあるが、なかなか厳しい。
（下記、厳密な証明になっているかは微妙だが、要点は書けているつもり。）
問題
(5巻18話の問題)
黒板に1から100までの整数が1つずつ書かれており、黒板から2つの整数$a, b$を選んで消し、新たに$\gcd(a^2b^2+3,a^2+b^2+2)$を書くという操作を繰り返し行う。
書かれている整数が1個になるまで繰り返す(★)とき、その整数は平方数でないことを示せ。
解法の概略
3や4で割った余りの世界でどうなるかを実験する
→3で割った余りの表を生成すると、規則性が見える。
実験※
See the Pen Untitled by kob58im (@kob58im) on CodePen.
※: ↑ Chat GPTで下記指示して書いてもらったコードをベースに作成
write a JavaScript code for calculating gcd.
write a JavaScript code to generate 10 x 10 table.
| $\gcd(a^2b^2+3,a^2+b^2+2)$ | a=3の倍数でない | a=3の倍数 |
|---|---|---|
| b=3の倍数でない | 3の倍数でない | 3の倍数 |
| b=3の倍数 | 3の倍数 | 3の倍数でない |
3の倍数でない・・・0
3の倍数・・・1
と置き換えてみると、下記のように加法的な性質をもつ
| A=0 | A=1 | |
|---|---|---|
| B=0 | 0 | 1 |
| B=1 | 1 | 0 |
これを繰り返し操作すると、どの順序で実行しても
1 2 3 4 5 6 7 8 9 ... 100に対しての繰り返し操作★は、
(0+0+1+0+0+1+0+0+1)×11 + 0 mod 2を計算するのと等価であり、これは1となるので、最後に残る数は3の倍数となる。
3の倍数が平方数であるためには、9の倍数である必要があるため、$\gcd(a^2b^2+3,a^2+b^2+2)$が 9の倍数である必要がある。
3の倍数となりえる組み合わせは、3の倍数 と 3の倍数でない ものを$a,b$としたときである。
$(3m\pm 1)^2(3n)^2+3\mod 9 = 3$であり、$\gcd(a^2b^2+3,X)$が9の倍数になることはない。
従って、最後に残る数は平方数ではない。