平方数を4で割った余り

方針

解答

⓪ 発想 — どう考え始めるか。 「$n^2$ の余り」を全部の $n$ で調べることはできない。そこで整数を有限のグループに分ける。

$4$ で割った余りが知りたいのだから、いちばん粗い分類から試す。偶数($n=2k$)と奇数($n=2k+1$)の2分類だ。

それぞれ2乗して $4$ で割れば、余りは $0$ と $1$ しか出ないと分かる。「余りが限られる」と分かれば、逆向きに「余り $3$ の数は平方数でない」という不可能の証明に使える。

$n$ を偶数・奇数で分ける。

$n$ が偶数($n=2k$)のとき:$n^2=4k^2$。余りは $0$。

$n$ が奇数($n=2k+1$)のとき:$n^2=4k^2+4k+1=4(k^2+k)+1$。余りは $1$。

よって、平方数を $4$ で割った余りは $0$ か $1$ のどちらかで、$2$ や $3$ にはならない。

$$n^2\text{ を }4\text{ で割った余りは }0\text{ または }1$$

応用:$4$ で割ると $3$ 余る整数を考える。もしそれが平方数なら、余りは $0$ か $1$ のはずなのに、余りが $3$ で矛盾する。だから『$4$ で割って $3$ 余る数』は平方数ではない($7,11,15,\dots$ はどれも平方数でない)。

(余りの性質は『できないこと(平方数でない)』を示すのに強い。)

発展 — 一歩先へ。 「平方数の余りは限られる」は、不可能の証明の定番兵器だ。$3$ で割ると余りは $0,1$ だけ、$8$ で割ると $0,1,4$ だけ。この在庫を持っておくと、「$x^2+y^2=(4$で割って$3$余る数$)$ に整数解なし」のような方程式の解の非存在が、余りの検分だけで示せる。

「全部は調べられないから、余りで有限のグループに落とす」という発想そのものが、整数論の背骨である。

別解

$4$ で割った余りで最初から4分類する、表の方法もある。

$n$ を $4$ で割った余りは $0,1,2,3$ のどれか。それぞれの $n^2$ の余りを表にする。

• 余り $0$: $n^2$ の余りは $0$
• 余り $1$: $n^2$ の余りは $1$
• 余り $2$: $n^2=(4k+2{)}^2=16k^2+16k+4$ で余り $0$
• 余り $3$: $n^2=(4k+3{)}^2=16k^2+24k+9$ で余り $1$

表の右列に現れるのは $0,1,0,1$。つまり余りは $0$ か $1$ だけだ。

分類を粗くする(偶奇の2分類)か、目的の $4$ に合わせる(4分類)か。どちらでも同じ結論に着く。表方式は機械的に進むぶん、$3$ で割った余りや $8$ で割った余りなど、他の設定にもそのまま横展開できるのが取り柄だ。