数学A / 整数の性質

余りによる整数の分類

★ 基礎余りによる分類

問題

整数 $n$ を $3$ で割った余りに着目して、 $n^{2}$ を $3$ で割った余りとしてありえるものをすべて求めよ。

ヒントを見る

整数を『 $3$ で割った余り』で $3$ グループ( $0, 1, 2$ )に分ける。各グループを $n = 3 k$ 、 $3 k + 1$ 、 $3 k + 2$ と文字で表し、 $n^{2}$ を計算して $3$ で割った余りを見よう。

解答・解説

方針

整数は無限にあるが、『 $3$ で割った余り』で分ければ $0, 1, 2$ の $3$ 種類だけ。各グループの代表で $n^{2}$ の余りを調べれば、すべての整数を調べたことになる。

解答

⓪ 発想 — どう考え始めるか。 「 $n$ はどんな整数でもよい」— 無限にある整数を、どうやって全部調べるのか。

答えは余りで仲間分けすること。 $3$ で割った余りは $0$ 、 $1$ 、 $2$ の $3$ 種類しかない。だから整数は

$n = 3 k, n = 3 k + 1, n = 3 k + 2 (k は整数)$

の $3$ グループに完全に分かれる。無限個の整数が、たった $3$ 通りに畳み込まれた。

あとはこの $3$ 通りそれぞれについて $n^{2}$ を計算し、 $3$ で割った余りを調べればよい。

$3$ 通りとも調べること。 $1$ つでも飛ばせば「すべての整数について」の証明にならない。余りによる分類は、無限を有限にする技である。

重要整数は余りで分類:

3

で割ると

n = 3 k, 3 k + 1, 3 k + 2

のどれか

整数 $n$ は、 $3$ で割った余りによって $3$ 種類に分けられる。 $n = 3 k$ 、 $n = 3 k + 1$ 、 $n = 3 k + 2$ ( $k$ は整数)のどれかだ。それぞれで $n^{2}$ を計算して、 $3$ で割った余りを調べる。

$n = 3 k$ のとき: $n^{2} = 9 k^{2} = 3 \cdot 3 k^{2}$ 。余りは $0$ 。

$n = 3 k + 1$ のとき: $n^{2} = 9 k^{2} + 6 k + 1 = 3 (3 k^{2} + 2 k) + 1$ 。余りは $1$ 。

$n = 3 k + 2$ のとき: $n^{2} = 9 k^{2} + 12 k + 4 = 3 (3 k^{2} + 4 k + 1) + 1$ 。余りは $1$ 。

どの場合も余りは $0$ か $1$ で、 $2$ にはならない。

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

まとめ:この『余りで分けて調べる』方法は、整数の証明の強力な道具になる。たとえば『 $3 n^{2} - 1$ は平方数にならない』も、この結果から言える(平方数の余りは $0, 1$ なのに、 $3 n^{2} - 1$ は余り $2$ だからだ)。

発展 — 一歩先へ。 同じ発想を $mod 4$ でやってみよう。整数は $2 k$ か $2 k + 1$ だから

$(2 k)^{2} = 4 k^{2} \equiv 0, (2 k + 1)^{2} = 4 k^{2} + 4 k + 1 \equiv 1 (mod 4)$

平方数を $4$ で割った余りは $0$ か $1$ だけ。

ここから、たちどころに次が分かる。 $2$ つの平方数の和 $x^{2} + y^{2}$ を $4$ で割った余りは

$0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 2$

の $3$ 通りしかない。 $3$ にはならない。

だから $x^{2} + y^{2} = 3$ 、 $x^{2} + y^{2} = 7$ 、 $x^{2} + y^{2} = 4003$ には整数解がない( $4003$ を $4$ で割ると $3$ 余る)。無限個の数を、一撃で否定した。

このように「どの数で割って見るか( $mod$ を何にするか)」を選ぶセンスが、整数問題の腕の見せどころだ。 $mod 3$ 、 $mod 4$ 、 $mod 8$ 、 $mod 9$ — 平方数、立方数、素数の性質に応じて、有効な法(modulus)が変わる。

大学入試の整数問題で「解が存在しないことを示せ」と言われたら、まず適当な数で割ってみる。 $9$ 割はこれで片がつく。余りの世界は、不可能を証明するための舞台なのだ。

答

$n^{2}$ を $3$ で割った余りは $0$ または $1$ ( $2$ にはならない)

別解

合同式という記号を使うと、この証明が数行で終わる。しかも、そこから面白い応用が生まれる。

合同式の書き方。 $n$ を $3$ で割った余りが $r$ のとき

$n \equiv r (mod 3)$

と書く。「 $mod$ 」は「割った余りで見る」という意味だ。

この記号のすごいところは、足し算・掛け算がそのままできること。

$a \equiv b, c \equiv d ⟹ a c \equiv b d (mod 3)$

だから、 $n \equiv r$ なら $n^{2} \equiv r^{2}$ が言える。 $3$ 通りの $r$ について $r^{2}$ を計算するだけでよい。

$n mod 3$	$n^{2} mod 3$
$0$	$0^{2} = 0$
$1$	$1^{2} = 1$
$2$	$2^{2} = 4 \equiv 1$

表 $1$ つで証明が終わった。 $n^{2}$ を $3$ で割った余りは $0$ か $1$ だけ。 $2$ は絶対に出てこない。

$(3 k + 2)^{2} = 9 k^{2} + 12 k + 4$ と展開する必要すらない( $9 k^{2}$ も $12 k$ も $3$ の倍数なので消え、 $4 \equiv 1$ が残る — 合同式はこの計算を自動でやってくれる)。

さて、この結論は何の役に立つのか。

「 $3$ で割って $2$ 余る数は、絶対に平方数ではない」 — これが使える。

たとえば、こう問われたとしよう。「 $2024$ は平方数か?」

わざわざ平方根を計算しなくてよい。 $2024$ の各位の和は $2 + 0 + 2 + 4 = 8$ なので、 $3$ で割った余りは $2$ 。

$2024 \equiv 2 (mod 3)$

平方数の余りは $0$ か $1$ しかない。だから $2024$ は平方数ではない — 証明終わり。(ちなみに $4 5^{2} = 2025$ で、惜しくも $1$ 違いだった。)

この手口は「不可能の証明」に絶大な威力を発揮する。

$x^{2} + y^{2} = 3$ を満たす整数はあるか? → $mod 4$ で考えると存在しないと分かる
ある方程式に整数解はあるか? → 適当な数で割った余りを見て、矛盾を探す

「実際に探して見つからない」ことと「存在しないと証明する」ことは、天と地ほど違う。 前者は永遠に終わらないが、後者は余りの表 $1$ つで片づく。

余りの世界は狭い(たった $3$ 通り)。だからこそ、そこで矛盾を見つければ、無限の世界の話に決着がつく。 整数論の最も鮮やかな武器である。

ポイント

整数は『 $k$ で割った余り』で $k$ 種類に分けられる
$n = 3 k, 3 k + 1, 3 k + 2$ の3通りを調べれば全整数を尽くせる
平方数を $3$ で割った余りは $0$ か $1$ (証明の道具になる)

よくある間違い

$n = 3 k + 1$ のときだけ調べて済ませる(3通りとも必要)
$(3 k + 2)^{2}$ の展開で $12 k$ の項を落とす
「余りは 0 か 1」を「 $n^{2}$ は 3 の倍数か 1」と読み違える(余りが 1 の数は 3 の倍数ではない)