整数の証明問題の多くは「数学的帰納法」や「背理法」を使う問題です。そしてこれらが整数問題に限らず、証明手段の代表格です。
●数学的帰納法で証明する問題
数学的帰納法には「整数n」が必要です。その意味で整数問題にはこれを使った証明問題がよく出るということになります。バリエーションとして、次のようなものがあります。
- n=1,2での成立を示し、nとn+1での成立を仮定してn+1での成立を示す（２段階前提）。
- nでの成立を仮定してn-1での成立を示し、n=1での成立を示す（逆向き）
教科書・参考書などでは、「nで成立するならn+1でも成立する」ことを証明するために、「n=kでの成立を仮定してn=k+1での成立を示す」という回りくどいことをしますが、与式をnの代わりにkで書くこと自体から手間がかかり、書き間違えも起きます。直接、「nで成立するならn+1でも成立する」ことを証明する方が手間と時間が節約できる上に、書き間違えの機会も減ります。本稿ではすべてこの方針で解答を書いています。
整数係数多項式の問題や割り算の問題などでも多用され、末尾の入試問題で紹介します。
●背理法で証明する問題
ある命題を証明する際に、その命題の否定を「仮定」して話をすすめるとつじつまが合わなくなり「矛盾」が生じます。これによって最初の「仮定」が誤りであることを示し、もとの命題が成り立つと結論する論法を背理法といいます。
有理数・無理数の問題nなど、整数nが出てこない問題は背理法を使って証明します。
●鳩の巣原理で証明する問題
鳩の巣原理は、「箱入れ原理」あるいは「部屋割り論法」と呼ばれ、n 個の物を m （<n）個の箱に入れるとき、少なくとも1個の箱には1個より多い物が中にある、という原理です。wikimediaにはその名のままの図が掲載されています（右図）。
調べた限りでは、鳩の巣原理を利用する問題は、以前は難関大で稀に出題されており、参考書にも掲載があるようですが、2000年以降は、1014年の東大の難問1問と2016年神戸大理系後期1問を除き、一般入試では見当たりません。
なお、入試問題の解答で「鳩の巣原理により」と書くことは間違いではないのですが、内容を知って使っていることを示す意味で、次のような記述が必要です。
【問題例】 3つの整数から、差が2の倍数になる2数を必ず選べることを示せ。
【解答例】
整数を2で割った余りは、0または1の 2通り である（＝巣の数）。いま、3つ の整数がある（＝鳩の数）。
鳩の巣原理（部屋割り論法）により、3つの整数のうち少なくとも2つは2で割った余りが一致する。したがって、その2数の差は2の倍数となる。