問題#B005 ★★☆☆
整数の2乗となる数を平方数という。
（１）平方数を$3$で割った余りは$0$か$1$に限られることを示せ。
（２）平方数を$4$で割った余りは$0$か$1$に限られることを示せ。
（３）平方数を$5$で割った余りは$0$か$1$か$4$に限られることを示せ。
《ポイント》
例えば$1$は$3$を法としたときの「平方剰余」であり、$2$は$3$を法としたときの「平方剰余」ではありません。証明では$3m \pm 1$などと置くか、合同式で片付けてしまいましょう。合同式については整数第２章第３節を参照してください。
《解答例》
以下、$m$は整数とする。
（１）
すべての整数は$3m$、$3m \pm 1$のいずれかの形で表される。
$3m$と表されるとき、$(3m)^2=9m^2$であり、$3$で割った余りは$0$である。
$3m \pm 1$と表されるとき、$(3m \pm 1)^2=9m^2 \pm 6m +1$であり、$3$で割った余りは$1$である。
よって平方数を$3$で割った余りは$0$か$1$に限られる。
□
（２）
すべての整数は$4m$、$4m \pm 1$、$4m+2$のいずれかの形で表される。
$4m$と表されるとき、$(4m)^2=16m^2$であり、$4$で割った余りは$0$である。
$4m \pm 1$と表されるとき、$(4m \pm 1)^2=16m^2 \pm 8m +1$であり、$4$で割った余りは$1$である。
$4m+2$と表されるとき、$(4m+2)^2=16m^2+16m+4$であり、$4$で割った余りは$0$である。
よって平方数を$4$で割った余りは$0$か$1$に限られる。
□
（３）
すべての整数は$5m$、$5m \pm 1$、$5m \pm 2$のいずれかの形で表される。
$5m$と表されるとき、$(5m)^2=25m^2$であり、$5$で割った余りは$0$である。
$5m \pm 1$と表されるとき、$(5m \pm 1)^2=25m^2 \pm 10m +1$であり、$5$で割った余りは$1$である。
$5m \pm 2$と表されるとき、$(5m \pm 2)^2=25m^2 \pm 20m+4$であり、$5$で割った余りは$4$である。
よって平方数を$5$で割った余りは$0$か$1$か$4$に限られる。
□
《コメント》
このように平方数の余りが限られるという事実は論証やディオファントス方程式を解く際に非常に重宝します。他にも様々な数で平方剰余を求めることができますが、問題を解く上で実用性があるのは大抵$3$か$4$を法としたときで、$5$を法として絞ることは滅多にありません。
今回は平方数で余りを考えましたが、その他の冪でも余りの数は限定されます。興味のある人は書き出してみると良い勉強になると思います。