余りで分けると証明が終わる - n の 2 乗と連続する整数の積

$n$ をどんな整数にしても、 $n^{2}$ を $3$ で割った余りは $0$ か $1$ にしかなりません。 $2$ は出てこない。

無限にある整数を 1 つずつ試したわけではありません。 $3$ で割った余りで 3 通りに分け、それぞれを調べただけです。

割り算の形を確かめる

整数 $a$ と正の整数 $b$ に対し、次をみたす $q$ と $r$ がただ 1 組だけ決まります^[1]。

$a = b q + r, 0 \leq r < b$

$q$ が商、 $r$ が余り。存在するだけでなく 1 組しかないところが効きます^[2]。

余りの範囲が $0$ から $b - 1$ に限られるので、整数全体が $b$ 個のグループに過不足なく分かれます。

$17 = 3 \times 5 + 2$ で、余りは $2$ 。 $17 = 3 \times 4 + 5$ と書いても等式は正しいものの、 $5$ は $3$ より大きいので余りではありません。

余りで整数を分ける

$3$ で割った余りが $0$ 、 $1$ 、 $2$ のどれになるかで、整数を 3 つの組に分けます。

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

どの整数もこのどれか 1 つにあてはまる。すべてを尽くしていて、しかも重なりがありません。

したがって、3 つの場合それぞれで成り立つと示せば、すべての整数について示したことになります。

上の行は $0, 1, 2$ をくり返し、下の行は $0, 1, 1$ をくり返します。 $2$ が現れないことが見てとれる。

例：n の 2 乗を 3 で割った余り

3 通りに分けて、それぞれ平方を計算します。

$(3 k)^{2} (3 k + 1)^{2} (3 k + 2)^{2} = 3 (3 k^{2}) = 3 (3 k^{2} + 2 k) + 1 = 3 (3 k^{2} + 4 k + 1) + 1$

余りはそれぞれ $0$ 、 $1$ 、 $1$ 。よって $n^{2}$ を $3$ で割った余りは $0$ か $1$ に限られます。

$n$ が $3$ の倍数のときだけ余りが $0$ になる。裏を返すと、 $n^{2}$ が $3$ の倍数なら $n$ も $3$ の倍数です。

例：n の 2 乗を 4 で割った余り

今度は偶奇の 2 通りで足ります。 $n = 2 k$ なら $n^{2} = 4 k^{2}$ で余り $0$ 。

$n = 2 k + 1$ なら $n^{2} = 4 (k^{2} + k) + 1$ で余り $1$ 。 $4$ で割ると $2$ や $3$ が余ることはありません。

さらに $k^{2} + k = k (k + 1)$ は連続する 2 整数の積なので偶数。だから奇数の平方は $8$ で割っても余りが $1$ です。

割る数	$n$ の分け方	$n^{2}$ の余り
$3$	$3 k$ 、 $3 k \pm 1$	$0$ 、 $1$
$4$	$2 k$ 、 $2 k + 1$	$0$ 、 $1$
$8$	$4 k$ 、 $4 k + 2$ 、奇数	$0$ 、 $4$ 、 $1$

例：平方数の下 1 桁

$10$ で割った余りを見ると、下 1 桁が分かります。 $n$ の下 1 桁が $0$ から $9$ の 10 通りで足りる。

平方の下 1 桁は $0, 1, 4, 9, 6, 5, 6, 9, 4, 1$ となります。現れるのは $0, 1, 4, 5, 6, 9$ の 6 種類だけ。

下 1 桁が $2$ 、 $3$ 、 $7$ 、 $8$ の数は平方数になりません。 $1358$ や $2087$ は、計算せずに除外できます。

例：3 の倍数になる 2 乗の和

$x^{2} + y^{2}$ が $3$ の倍数なら、 $x$ も $y$ も $3$ の倍数だと示せます。

平方を $3$ で割った余りは $0$ か $1$ でした。和が $3$ の倍数、つまり余り $0$ になる組み合わせを探します。

$0 + 0 = 0$ 、 $0 + 1 = 1$ 、 $1 + 1 = 2$ 。余りが $0$ になるのは $0 + 0$ だけなので、両方とも $3$ の倍数です。

この議論が通るのは、平方の余りが $0$ と $1$ の 2 種類しかないからです。

もし $2$ も現れるなら $1 + 2 = 3$ の組も余り $0$ になり、結論が言えなくなる。

連続する整数の積

連続する 2 つの整数 $n$ 、 $n + 1$ には、必ず偶数が 1 つ含まれます。だから積は $2$ の倍数。

連続する 3 つなら、 $2$ の倍数と $3$ の倍数がそれぞれ必ず入ります。積は $6$ の倍数になる。

窓をどこへずらしても、緑と赤が 1 つずつ入ります。 $2$ と $3$ は互いに素なので、積は $6$ で割り切れる。

一般には k 個で k の階乗

連続する $k$ 個の整数の積は、 $k!$ で割り切れます。二項係数がつねに整数になることと同じ事実です^[3]。

$(k n) = \frac{n ( n - 1 ) ( n - 2 ) \dots ( n - k + 1 )}{k !}$

左辺は「 $n$ 個から $k$ 個を選ぶ場合の数」なので整数。すると右辺の分子は $k!$ で割り切れるほかありません。

連続 4 個なら $4! = 24$ の倍数、連続 5 個なら $120$ の倍数。 $k$ が大きくなるほど強い主張になります。

例：n の 3 乗から n を引く

$n^{3} - n$ が $6$ の倍数だと示します。因数分解から始めるのが早い。

$n^{3} - n = n (n^{2} - 1) = (n - 1) n (n + 1)$

連続する 3 整数の積になりました。したがって $6$ の倍数です。 $n = 4$ なら $60$ 、 $n = 5$ なら $120$ 。

余りで分類しても示せます。ただ、連続する整数の形に持ち込むほうが手数は少ない。

例：n の 5 乗から n を引く

$n^{5} - n$ は $30$ の倍数になります。 $30 = 2 \times 3 \times 5$ なので、 $6$ と $5$ に分けて考える。

$n^{5} - n = (n - 1) n (n + 1) (n^{2} + 1)$

前の 3 つが連続なので $6$ の倍数。残るのは $5$ で割り切れるかどうかです。

$n$ が $5$ の倍数なら終わり。そうでなければ $n^{2}$ を $5$ で割った余りは $1$ か $4$ で、 $n^{4}$ の余りは $1$ になります。

$n^{5} - n = n (n^{4} - 1)$ の $n^{4} - 1$ が $5$ の倍数。どちらの場合も $5$ で割り切れました。

答えを確かめる

主張が正しそうかは、小さい数で試すのが早い。 $n = 1$ から $6$ まで $n^{3} - n$ を並べると $0, 6, 24, 60, 120, 210$ 。

どれも $6$ の倍数です。反例が 1 つでも出れば、証明を始める前に誤りが分かります。

場合分けが尽くせているかも確かめます。 $3$ で割るなら 3 通り、 $4$ なら 4 通り。数が合わなければ、どこかを落としている。

整数 $n$ に対して $n^{2}$ を $5$ で割った余りとして、現れないものはどれですか。

__RESULT__

$n$ を $5 k, 5 k \pm 1, 5 k \pm 2$ に分けると、 $n^{2}$ の余りは $0$ 、 $1$ 、 $4$ の 3 種類になります。 $2$ と $3$ は現れません。

まちがえやすい点

場合分けを

3 k

と

3 k + 1

だけで止める。

3 k + 2

を落とすと証明になりません。

余りに

b

以上の値をとる。

0

から

b - 1

の範囲に収めます。

負の整数を忘れる。

n = - 1

も

3 k + 2

の形（

k = - 1

）に入ります。

連続する 3 整数の積を

2

の倍数までで止める。

3

の倍数も必ず含まれます。

6

の倍数を示すのに

2

と

3

を別々に言わず、

6

の倍数を直接探す。分けたほうが速い。

n^{2}

の余りだけを見て、

n

の余りを言い忘れる。逆向きの主張は別に確かめます。

具体例をいくつか試しただけで証明を終える。すべての場合を尽くす必要があります。

余りで分ければ、無限にある整数が有限個の場合に変わる。証明の道具としては、これがいちばん手前にあります。

参考文献

Euclidean division - Wikipedia

Division mit Rest - Wikipedia

Binomial coefficient - Wikipedia

$n$ を $3k$、$3k+1$、$3k+2$ の 3 通りに分けて平方すると、余りは $0$、$1$、$1$。$2$ はどこにも現れません。無限にある整数が 3 つの場合に縮む、これが余りで分ける効き目です。$4$ で割れば $0$ か $1$、奇数の平方なら $8$ で割っても $1$ が残る。平方数の下 1 桁が $2, 3, 7, 8$ にならない理由、$x^2 + y^2$ が $3$ の倍数なら両方とも $3$ の倍数になる筋道、連続する $3$ 整数の積が $6$ の倍数になる話から $n^5 - n$ が $30$ の倍数になるところまで並べました。