【基本】余りによる整数の分類
ここでは、余りによって整数を分類することで、整数に関する証明問題が解けるようになる例を見ていきます。
整数の2乗を4で割った余り
整数のうち、2で割り切れるものを偶数、割り切れないものを奇数といいました。これらはダブっていないし、漏れているものもありません。整数はこの2種類に分類できます。
なので、整数に関して何か言いたいときに、偶数と奇数に分けるという方法を使える場合があります。
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で割った余りで分類しました。
どのように分類することがいいのかは、いくつか問題を解いてみにつけていくようにしましょう。
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になることがわかります。
こうして、余りによって分類し、場合分けをすることで、証明することができました。
おわりに
ここでは、余りによる整数の分類が、整数に関する証明問題に応用できる例を見ました。いつも応用できるとは限りませんが、こうした分類による場合分けで証明がしやすくなる例がある、ということをおさえておきましょう。
