対偶を用いる整数の証明(3の倍数)

方針

解答

⓪ 発想 — どう考え始めるか。 「$n^2$ が3の倍数 ⟹ $n$ が3の倍数」を直接示そうとすると、$n^2$ の情報から $n$ を復元する向きで進みにくい。

そこで対偶「$n$ が3の倍数でない ⟹ $n^2$ も3の倍数でない」に切り替える。仮定が「$n=3k\pm 1$ と書ける」という使いやすい形になるのが対偶の御利益だ。

あとは2乗して、3で割った余りを計算するだけ。どちらの場合も余り $1$ で、3の倍数にならない。

① 対偶をとる。 示すべき対偶は「$n$ が $3$ の倍数でないならば $n^2$ も $3$ の倍数でない」。

② 余りで場合分け。 $n$ が $3$ の倍数でないとき、$n=3k+1$ または $n=3k+2$($=3(k+1)-1$)、まとめて $n=3k\pm 1$。 $$n^2=(3k\pm 1{)}^2=9k^2\pm 6k+1=3(3k^2\pm 2k)+1.$$ ③ 余り $1$。 $n^2$ は $3$ で割ると余り $1$ で、$3$ の倍数でない。よって対偶が成り立ち、元の命題「$n^2$ が $3$ の倍数 $\Rightarrow$ $n$ が $3$ の倍数」も真。

まとめ 対偶「$n$ が $3$ の倍数でない $\Rightarrow$ $n^2$ も $3$ の倍数でない」を、$n=3k\pm 1$ の $2$ 乗が余り $1$ になることで示す。命題(対偶)と整数の融合。$\sqrt{3}$ が無理数の証明にも使う。

発展 — 一歩先へ。 この命題($3\mid n^2\Rightarrow 3\mid n$)は、$\sqrt{3}$ の無理性証明の心臓部品そのもの(前問の $p=3$ の場合で使った性質)。また対偶の技は「余りで分類すると仮定が使いやすくなる」場面全般で有効で、たとえば「$n^2+1$ が3の倍数になる $n$ は存在しない」($n^2$ の余りは $0,1$ のみ)も同じ表から即答できる。

別解

素数の性質で直接(対偶を経由しない1行)。 $3$ は素数だから、次の性質が使える:

素数 $p$ が積 $ab$ を割り切るなら、$p$ は $a$ か $b$ の少なくとも一方を割り切る。

$n^2=n\times n$ に適用すると、$3\mid n^2$ から $3\mid n$ または $3\mid n$ — すなわち $3\mid n$。1行で終わる。

対偶+余りの場合分け(本解)は、この素数の性質を「余りの計算」で手作りしていることに当たる(余り $1,2$ の2乗が $1$ になる、という表がその中身)。素数の性質を既知として使ってよい場面なら直接1行、性質そのものの根拠から書く場面なら対偶 — 答案の文脈で使い分けたい。ちなみにこの命題は、$\sqrt{3}$ の無理性証明(前問の $p=3$)の中でまさに部品として働く。