今年の後期試験も無事に終了し、入試シーズンが一段落しました。今回は北海道大学の後期数学に出題された整数問題を取り上げます。
次の問に答えよ。
（１）整数$m$に対して、$m^2$を$4$で割った余りは$0$または$1$であることを示せ。
（２）自然数$n$、$k$が$$25 \times 3^{n}=k^{2}+176 \quad \cdots \cdots(*)$$を満たすとき、$n$は偶数であることを示せ。
（３）（２）の関係式$(*)$を満たす自然数の組$(n,k)$をすべて求めよ。
（2021年北海道大学 後期理系 第4問）
考え方
平方剰余は整数分野の定番です。特に指数関数を含むようなディオファントス方程式の解を絞り込む際には必須のテクニックと言えます。（２）をヒントにして関係式$(*)$を因数分解すると解の候補が絞り込めます。
解答例
（１）
$m$が偶数のとき、$m^2$は$4$の倍数となるから、$m^2$を$4$で割った余りは$0$である。
$m$が奇数のとき、$m=2i+1$（$i$は整数）と置けて、$$m^2=(2i+1)^2=4(i^2+i)+1$$となるから、$m^2$を$4$で割った余りは$1$である。
よって、整数$m$に対して、$m^2$を$4$で割った余りは$0$または$1$であることが示された。
□
（２）
$n$が奇数であるとすると、$n=2j+1$（$j$は負でない整数）と置ける。このとき関係式$(*)$の左辺について、$$\begin{align} & \quad \ 25 \times 3^{n} \\ &=25 \times 3^{2j+1} \\ &=25 \times 3 \times 9^{j} \\ & \equiv 1 \times 3 \times 1^j \pmod{4} \\ &=3 \end{align}$$となるから、$n$が奇数のとき左辺を$4$で割った余りは$3$となる。ここで、$k$は整数であるから（１）より$k^{2}$を$4$で割った余りは$0$または$1$であり、$176$を$4$で割った余りは$0$であるから、関係式$(*)$の右辺を$4$で割った余りは$3$にならない。これは不合理である。
したがって、関係式$(*)$を満たす$n$は奇数ではない、即ち偶数である。
□
（３）
（２）より、$n$は偶数であるから、正の整数 $l$ を用いて $n=2\,l$ と置ける。このとき関係式$(*)$は$$25 \times 3^{2l}=k^{2}+176$$ $$\therefore (5 \times 3^l)^2-k^2=176$$ $$\therefore (5 \times 3^l-k)(5 \times 3^l+k)=2^4 \times 11$$と式変形できる。
ここで、$5 \times 3^l-k$ と $5 \times 3^l+k$ の差は$2k$となり偶数であるから、この2数の偶奇は一致する。このことと$$0<5 \times 3^l-k<5 \times 3^l+k$$に注意すると、この2数の組み合わせは以下のものに限られる。$$\begin{array}{cc|c}
& 5 \times 3^l-k & 5 \times 3^l+k \\
\hline ① & 2 & 2^{3} \times 11 \\
② & 2^{2} & 2^{2} \times 11 \\
③ & 2^{3} & 2 \times 11
\end{array}$$①のとき $2k=2^{3} \times 11-2$ より $k=43$ となるから、$5 \times 3^l-43=2$ を解いて $l=2$ を得る。よって$$(n,k)=(4,43)$$は求める自然数組の一つである。
②のとき $2k=2^{2} \times 11-2^{2}$ より $k=20$ となるが、$5 \times 3^l-20=4$ を満たすような整数 $l$ は存在しない。
③のとき $2k=2\times 11-2^{3}$ より $k=7$ となるから、$5 \times 3^l-7=8$ を解いて $l=1$ を得る。よって$$(n,k)=(2,7)$$は求める自然数組の一つである。
以上より、関係式$(*)$を満たす自然数の組は$$(n,k)=\color{red}{(2,7),\,(4,43)}$$と求められる。
後期試験としては標準的な整数問題でした。平方剰余の組み合わせから文字の条件を絞り込んでいく方法はディオファントス方程式（不定方程式）を解くときの定石です。丁寧な誘導設問が設置されているので上手く乗りたいですね。
（２）では、$n$が奇数だとすると矛盾する、として$n$が偶数に限ることを証明しています。この矛盾の根源が平方剰余という訳です。今回は$4$を法とする平方数の剰余を考えましたが、$3$や$5$を法とする平方数の剰余にも制限が生じるので式の形によっては別の数を法として考えても良いでしょう。本問の場合は $\bmod 4$ を考えるのが最も効果的です。
因数分解する際は「文字式＝定数」という形になるように変形する必要があります。定数の素因数は有限個しかないので、この形に式変形できれば解の候補を絞り込めるからです。本問の方程式には$176$という定数項があからさまに存在するので、方針に迷った人は少ないのではないかと思います。因数分解によって解の候補を絞り込むときは、整数組の大小や偶奇の組み合わせに注意することで、記述の手間を大きく軽減することができます。
ディオファントス方程式については当サイトの創作整数問題シリーズでも何題か扱っているので参考にしてみて下さい。