対偶と余りによる整数の証明

方針

解答

⓪ 発想 — どう考え始めるか。 「$a^2+b^2$ が $3$ の倍数 $\Rightarrow$ $a,b$ とも $3$ の倍数」は直接は示しにくい。こういうときは対偶をとる。

対偶は「$a,b$ の少なくとも一方が $3$ の倍数でない $\Rightarrow$ $a^2+b^2$ は $3$ の倍数でない」。

急所は「平方を $3$ で割った余り」。整数を $3$ で割った余り $0,1,2$ で分類すると、平方の余りは $0$ か $1$ だけ($0^2\equiv 0$、$1^2\equiv 1$、$2^2\equiv 1$)。しかも余り $0$ になるのは元が $3$ の倍数のときだけ。だから一方でも $3$ の倍数でなければ、和の余りは $0$ にならない。

① 平方の余りを調べる。 整数を $3$ で割った余りで分類する。余り $0,1,2$ の数の平方は、$3$ で割るとそれぞれ $0,1,1$($2^2=4=3+1$ に注意)。よって整数の平方を $3$ で割った余りは $0$ か $1$ に限られ、余りが $0$ になるのは元の数が $3$ の倍数のときだけ。

② 対偶を示す。 $a$ が $3$ の倍数でないとすると $a^2$ の余りは $1$。$b^2$ の余りは $0$ か $1$。和 $a^2+b^2$ の余りは $1+0=1$ または $1+1=2$ で、どちらも $0$ でない。よって $a^2+b^2$ は $3$ の倍数でない。$b$ が $3$ の倍数でない場合も同様。

③ 結論。 対偶が真なので、もとの命題も真。すなわち $a^2+b^2$ が $3$ の倍数ならば、$a,b$ はともに $3$ の倍数である。(証明終)

まとめ:「和が $3$ の倍数 ⟹ 各項が…」の証明は、対偶+「$3$ で割った余りで分類」の合わせ技。平方の余りが $0,1$ しか出ない(=$2$ が出ない)ことが、和の余りを縛る鍵になる。

発展 — 一歩先へ。 平方数を $3$ で割った余りが $\{0,1\}$ に限られることは、$x^2+y^2=3z^2$ が自明でない整数解をもたない証明にも使える(無限降下法)。$4$ で割った余り($\{0,1\}$)を使えば「$3$ で割って $3$ 余る数は $2$ 平方和で書けない」など、平方剰余は整数論の強力な道具だ。

別解

別解 — 平方の余りの表を作って直接確かめる(苦手な人向け)。 対偶をとる前に、整数を $3$ で割った余りごとに $a^2$ の余りを表にする。

平方の余りは $0$ か $1$ しか出ない。$a^2+b^2$ の余りは、$(a^2\mathrm{mod}3)+(b^2\mathrm{mod}3)$ の組合せで $0+0=0$、$0+1=1$、$1+1=2$ の $3$ 通り。

$a^2+b^2\equiv 0(\mathrm{mod}3)$ になるのは $0+0$ のときだけ。つまり $a^2\equiv 0$ かつ $b^2\equiv 0$、すなわち $a\equiv 0$ かつ $b\equiv 0(\mathrm{mod}3)$。

これはまさに「$a,b$ ともに $3$ の倍数」。対偶(本解)を経由せず、余りの組合せ表で「和の余りが $0$ になるのは両方 $0$ のときだけ」と直接読めば、同じ結論に着く。$1+1=2\ne 0$ が“逃げ道をふさぐ”のがポイントだ。