【基本】余りによる整数の分類

ここでは、余りによって整数を分類することで、整数に関する証明問題が解けるようになる例を見ていきます。

【広告】

整数の2乗を4で割った余り

整数のうち、2で割り切れるものを偶数、割り切れないものを奇数といいました。これらはダブっていないし、漏れているものもありません。整数はこの2種類に分類できます。

なので、整数に関して何か言いたいときに、偶数と奇数に分けるという方法を使える場合があります。

例題1
$n$ を整数とするとき、 $n^2$ を4で割った余りが0か1になることを示しなさい。

4で割った余りなので、2や3になる可能性もありますが、そういうことはない、ということですね。

パッとわかるのは、 $n$ が偶数のときでしょう。 $n$ が2の倍数なら、 $n^2$ は4の倍数になることはすぐにわかります。なので、4で割った余りは0となります。

一方、奇数の場合はどうでしょうか。奇数の場合に対応するのは、余りが1のときなのでしょうが、余りが1になること、余りが3にならないことを、一般的な状況で示すには難しいです。

そこで、文字を使って整数を表す、という方法が使えます。 $n$ が偶数なら、2で割ったときの商を使って、「2×商」、と書けるし、奇数なら、「2×商+1」と書けます。これを使って式変形をすれば、証明することができます。

以下、場合分けをして考えてみましょう。

(1) $n$ が偶数のとき

このときは、 $n=2k$ となる整数 $k$ が存在します。よって、\[ n^2=(2k)^2=4k^2 \]となり、 $k^2$ は整数だから、 $n^2$ を4で割った余りは0となります。

(2) $n$ が奇数のとき

このときは、 $n=2k+1$ となる整数 $k$ が存在します。よって、
\begin{eqnarray}
n^2
&=&
(2k+1)^2 \\[5pt] &=&
4k^2+4k+1 \\[5pt] &=&
4(k^2+k)+1 \\[5pt] \end{eqnarray}となります。 $(k^2+k)$ は整数だから、 $n^2$ を4で割った余りは1となります。

(1)(2)から、整数 $n$ の2乗を4で割った余りは、0か1になることがわかります。

こうして、整数全体を、2で割った余りで分け、それぞれの場合で考えることで、証明しやすくなる場面があります。

整数の2乗を3で割った余り

先ほどは、整数を2で割った余りで分けましたが、他の数で割った余りで分類することももちろんできます。例えば、3で割った余りで分類するなら、どんな整数でも、\[ 3k,3k+1,3k+2 \]のどれかの形で書ける( $k$ は整数)、となります。

一般には、正の整数 $m$ に対して、どんな整数でも、\[ mk,mk+1,\cdots mk+(m-1) \]のどれかの形で書けます( $k$ は整数)。ダブりもモレもありません。

ただ、整数に関する問題を証明するときに、これらの分類がいつも役立つかはわからないし、何で分類すればいいかは問題によって異なります。余りに関する問題ではよく使われますが、それだけにとどまりません。また、先ほどの例題では、4で割った余りを考えるために、整数を2で割った余りで分類しました。

どのように分類することがいいのかは、いくつか問題を解いてみにつけていくようにしましょう。

例題2
$n$ を整数とするとき、 $n^2$ を3で割った余りが0か1になることを示しなさい。

3で割った余りなので、2になる可能性もありますが、そういうことはない、ということですね。

3で割った余りについて考えたいので、 $n$ も3で割った余りによって分類すればいいのではないか、と予想を立てて考えていきます。3で割ったときの余りが、0, 1, 2 のどれかで場合分けをしましょう。

整数 $n$ は、ある整数 $k$ を使って、\[ 3k,3k+1,3k+2 \]のどれかで表すことができます。3で割ることを考えれば、 $k$ が商で、余りはこの3種類のどれか、ということですね。

(1) $n=3k$ のとき

\[ n^2=(3k)^2=3\times 3k^2 \]となり、 $3k^2$ は整数だから、 $n^2$ を3で割った余りは0となります。

(2) $n=3k+1$ のとき

このときは、
\begin{eqnarray}
n^2
&=&
(3k+1)^2 \\[5pt] &=&
9k^2+6k+1 \\[5pt] &=&
3(3k^2+2k)+1 \\[5pt] \end{eqnarray}となります。 $(3k^2+2k)$ は整数だから、 $n^2$ を3で割った余りは1となります。

(3) $n=3k+2$ のとき

このときは、
\begin{eqnarray}
n^2
&=&
(3k+2)^2 \\[5pt] &=&
9k^2+12k+4 \\[5pt] &=&
3(3k^2+4k+1)+1 \\[5pt] \end{eqnarray}となります。 $(3k^2+4k+1)$ は整数だから、 $n^2$ を3で割った余りは1となります。

(1)(2)(3)から、整数 $n$ の2乗を3で割った余りは、0か1になることがわかります。

こうして、余りによって分類し、場合分けをすることで、証明することができました。

おわりに

ここでは、余りによる整数の分類が、整数に関する証明問題に応用できる例を見ました。いつも応用できるとは限りませんが、こうした分類による場合分けで証明がしやすくなる例がある、ということをおさえておきましょう。