整数の証明問題は、入試で最も「考える力」が問われる分野です。
偶奇による場合分け、余りによる分類、背理法 ── 証明の武器を原理から理解すれば、
どんな問題にも自分の力で立ち向かえます。
整数の証明で最も基本的なテクニックが、偶奇による場合分けです。 すべての整数は偶数か奇数のどちらかに分類できます。 偶数は $2k$、奇数は $2k+1$（$k$ は整数）と表せるので、 この2つの場合に分けて調べれば、すべての整数を尽くしたことになります。
なぜこれが証明に有効なのでしょうか？ それは、整数の性質の多くが「2で割った余り」に依存しているからです。 たとえば「$n^2$ が偶数ならば $n$ も偶数」を示したいとき、 $n$ が偶数の場合と奇数の場合を調べれば、完全に検証できます。
整数の証明で場合分けが有効な理由は明快です。 整数は無限にあるので、1つずつ確認することは不可能。 しかし、偶数・奇数のように有限個のグループに分類すれば、各グループの代表で確認するだけで、 すべての整数について証明したことになります。
偶数を $2k$、奇数を $2k+1$ と書くのは、「このグループの任意の要素」を1つの文字で代表させる技法です。 $k$ が任意の整数を動くので、$2k$ はすべての偶数を代表します。
整数 $n$ について $n^2 + n$ が偶数であることを証明しましょう。
(i) $n$ が偶数のとき：$n = 2k$（$k$ は整数）とおくと、
$$n^2 + n = (2k)^2 + 2k = 4k^2 + 2k = 2(2k^2 + k)$$
$2k^2 + k$ は整数なので、$n^2 + n$ は偶数。
(ii) $n$ が奇数のとき：$n = 2k+1$（$k$ は整数）とおくと、
$$n^2 + n = (2k+1)^2 + (2k+1) = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)$$
$2k^2 + 3k + 1$ は整数なので、$n^2 + n$ は偶数。
(i)(ii)より、すべての整数 $n$ について $n^2 + n$ は偶数である。 $\square$
実はこの問題には、場合分けを使わないエレガントな別解もあります。 $n^2 + n = n(n+1)$ と因数分解すると、$n$ と $n+1$ は連続する2整数なので、 どちらか一方は必ず偶数です。よって積 $n(n+1)$ は偶数です。
✕ 誤：「$a$ が偶数、$b$ が奇数のとき、$a = 2k$、$b = 2k+1$ とおく」
○ 正：「$a = 2k$、$b = 2l+1$（$k, l$ は整数）とおく」
$a$ と $b$ は独立な整数なので、異なる文字を使って表す必要があります。 $a = 2k$、$b = 2k+1$ と書くと、$b = a + 1$（連続する整数）という余分な条件を課してしまいます。 ただし、1つの整数 $n$ が偶数のとき $n = 2k$、奇数のとき $n = 2k+1$ と書くのは問題ありません。
偶奇の場合分けが威力を発揮するのは、「2乗」が絡む証明です。 なぜなら、偶数の2乗は4の倍数、奇数の2乗を4で割ると1余る、という強い性質があるからです。
偶数の2乗：$(2k)^2 = 4k^2$ → 4の倍数
奇数の2乗：$(2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1$ → 4で割ると1余る
$n^2 + n$ が偶数であることを示すとき、式変形の最後で $2 \times (\text{整数})$ の形にすることが必要です。
✕ 誤：$n = 2k+1$ のとき $n^2 + n = 4k^2 + 6k + 2$。「偶数っぽいから偶数」
○ 正：$n^2 + n = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)$。「$2k^2 + 3k + 1$ は整数なので偶数」
最終的に $2 \times (\text{整数})$ の形まで変形し、カッコ内が整数であることを明記しましょう。
大学数学では、整数を2で割った余りで分類することを「$\mathbb{Z}/2\mathbb{Z}$（2を法とする剰余類）」と呼びます。 偶数は $\bar{0}$、奇数は $\bar{1}$ と表記し、たった2つの「数」しかない世界を考えます。
この世界では $\bar{1} + \bar{1} = \bar{0}$（奇数＋奇数＝偶数）、$\bar{1} \times \bar{1} = \bar{1}$（奇数×奇数＝奇数） といった演算ができます。これは暗号理論やコンピュータサイエンスで広く使われる有限体の最も簡単な例です。
偶奇の場合分けは「2で割った余り」による分類でした。 同じ発想を一般化して、$n$ で割った余りによって整数を分類するのが、 このセクションのテーマです。
たとえば、3で割った余りで分類すると、すべての整数は $3k$、$3k+1$、$3k+2$（$k$ は整数）の3種類に分けられます。 「3の倍数」に関する性質を証明したいとき、この3パターンで場合分けすれば完全です。
整数の証明で場合分けの仕方に迷ったら、「何の倍数であることを示したいか」を考えてください。
・「偶数であること」を示したい → 2で割った余りで分類（2パターン）
・「3の倍数であること」を示したい → 3で割った余りで分類（3パターン）
・「6の倍数であること」を示したい → 2の倍数 かつ 3の倍数 を別々に示す
証明の目標が場合分けの仕方を自然に決めてくれるのです。
整数 $n$ について、$n^3 - n$ が6の倍数であることを証明します。 6の倍数であることは、「2の倍数 かつ 3の倍数」であることと同値です。
$n^3 - n = n(n^2 - 1) = n(n-1)(n+1) = (n-1)n(n+1)$
これは連続する3整数の積です。
2の倍数であること：連続する3整数のうち、少なくとも1つは偶数なので、積は2の倍数。
3の倍数であること：連続する3整数のうち、ちょうど1つは3の倍数なので、積は3の倍数。
2と3は互いに素なので、$(n-1)n(n+1)$ は $2 \times 3 = 6$ の倍数である。 $\square$
上の証明では因数分解がうまく効きましたが、常にこのようにきれいに分解できるとは限りません。 そのようなときは、余りで直接場合分けします。
整数 $n$ を3で割った余りで場合分けします。
(i) $n = 3k$ のとき：$n^2 = 9k^2 = 3(3k^2)$ → 余り $0$
(ii) $n = 3k+1$ のとき：$n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$ → 余り $1$
(iii) $n = 3k+2$ のとき：$n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$ → 余り $1$
(i)(ii)(iii)より、$n^2$ を3で割った余りは $0$ か $1$ である。 $\square$
この結果は非常に強力です。$n^2$ を3で割った余りが2になることは絶対にないのです。 これは「$3k+2$ の形の整数は、どんな整数の2乗にもなれない」ことを意味します。
3で割って2余る整数は $3k+2$ と書けますが、$3k-1$ と書いても同じことです （$3k+2 = 3(k+1) - 1$）。
✕ 誤：「$n = 3k-1$ とすると $n^2 = 9k^2 - 6k + 1 = 3(3k^2 - 2k) + 1$。余り1。 でも $n = 3k+2$ の場合はまた別に調べなきゃ」
○ 正：$3k+2$ と $3k-1$ は同じグループを表すので、どちらか一方を調べれば十分。 答案では統一的に $3k, 3k+1, 3k+2$ とするか、$3k, 3k \pm 1$ とするかを決めて統一しましょう。
整数の2乗を $n$ で割った余りには「制限」があります。 $n^2$ を3で割った余りは0か1だけで、2にはなりません。 $n^2$ を4で割った余りは0か1だけで、2にも3にもなりません。
この「ありえないパターンの発見」こそが、余りによる分類の真の威力です。 「$n^2 + m^2$ が $3k + 2$ の形にならない」ことなど、単純な計算では見えない性質が、 余りの分類によって明らかになります。
「$n$ で割った余りが等しい」ことを数学では合同式で表します。 $a$ と $b$ を $n$ で割った余りが等しいとき、$a \equiv b \pmod{n}$ と書きます。
合同式には通常の等式と同じように加減乗の演算が成り立ちます。 $a \equiv b \pmod{n}$ かつ $c \equiv d \pmod{n}$ ならば、 $a + c \equiv b + d$、$ac \equiv bd \pmod{n}$ です。
大学の整数論（数論）では、合同式は基本言語として使われます。 高校の「余りで分類して計算」は、合同式の考え方を日本語で書いたものにほかなりません。
整数の証明のなかでも、背理法は特別な位置を占めています。 背理法とは、「結論の否定を仮定して矛盾を導くことで、もとの結論が正しいことを示す」証明方法です。
なぜ背理法が必要なのでしょうか？ 「$\sqrt{2}$ は無理数である」を直接証明しようとすると、 「有理数でないこと」、つまり「どんな分数 $\frac{p}{q}$ でも表せないこと」を、 すべての分数について確認しなければなりません。これは不可能です。
そこで発想を逆転させます。 「もし $\sqrt{2}$ が有理数だったら」と仮定して、矛盾が生じることを示すのです。
背理法が特に威力を発揮するのは、「〜でない」「〜は存在しない」という否定的な命題の証明です。
「$\sqrt{2}$ は有理数でない」を直接示すのは困難ですが、 「$\sqrt{2}$ が有理数であると仮定する」と、$\sqrt{2} = \frac{p}{q}$ という具体的な式が手に入ります。 式があれば計算ができ、矛盾を導けます。
背理法の最大の利点は、「否定の仮定」が新しい条件（計算の手がかり）を与えてくれることです。
仮定：$\sqrt{2}$ が有理数であると仮定する。 すると、互いに素な正の整数 $p, q$ を用いて $\sqrt{2} = \dfrac{p}{q}$ と表せる。
Step 1：両辺を2乗して整理する。
$$2 = \frac{p^2}{q^2} \quad \Longrightarrow \quad p^2 = 2q^2 \quad \cdots ①$$
Step 2：$p$ が偶数であることを示す。
①より $p^2$ は偶数。ここで、もし $p$ が奇数なら $p^2$ も奇数（奇数×奇数＝奇数）となり矛盾。 よって $p$ は偶数。$p = 2m$（$m$ は正の整数）とおける。
Step 3：$q$ も偶数であることを示す。
$p = 2m$ を①に代入すると、$(2m)^2 = 2q^2$、すなわち $4m^2 = 2q^2$。
$$q^2 = 2m^2$$
Step 2と同じ論法で、$q^2$ が偶数なので $q$ も偶数。
Step 4：矛盾を導く。
$p$ も $q$ も偶数なので、$p$ と $q$ は公約数2をもつ。 これは「$p$ と $q$ は互いに素」という仮定に矛盾する。
結論：$\sqrt{2}$ が有理数であるという仮定は誤り。 よって $\sqrt{2}$ は無理数である。 $\square$
背理法では「結論の否定」を仮定します。この否定を正しく取ることが第一関門です。
✕ 誤：「$\sqrt{2}$ は無理数である」の否定を「$\sqrt{2}$ は整数である」とする
○ 正：「$\sqrt{2}$ は無理数である」の否定は「$\sqrt{2}$ は有理数である」
「無理数でない ＝ 有理数」です。「有理数」よりも狭い「整数」と否定してしまうと、 証明が不完全になります。否定は「ちょうど裏返し」であることを意識しましょう。
✕ 誤：「$\sqrt{2} = \frac{p}{q}$（$p, q$ は正の整数）とおく」→ 矛盾を導けない
○ 正：「$\sqrt{2} = \frac{p}{q}$（$p, q$ は互いに素な正の整数）とおく」
「互いに素」という条件がなければ、$p$ と $q$ がともに偶数であっても矛盾が起きません。 有理数を既約分数で表すことが、背理法のカギです。 既約分数の存在は「有理数は必ず約分できる」という事実から保証されます。
同じ論法は $\sqrt{3}$、$\sqrt{5}$ などにも適用できます。 $\sqrt{3}$ の場合は「$p^2 = 3q^2$ から $p$ が3の倍数であること」を示す必要があり、 ここで Section 2 で学んだ「余りによる分類」が活躍します。
$p$ が3の倍数でないと仮定すると、$p = 3k+1$ または $p = 3k+2$ です。 いずれの場合も $p^2$ を3で割った余りは1になるので、$p^2$ が3の倍数になりません。 しかし $p^2 = 3q^2$ より $p^2$ は3の倍数のはずなので矛盾。よって $p$ は3の倍数です。
素数 $p$ について、$\sqrt{p}$ が無理数であることの証明は以下の構造をもちます。
1. $\sqrt{p} = \frac{a}{b}$（$a, b$ は互いに素な正の整数）と仮定
2. $a^2 = pb^2$ を導く
3. $a^2$ が $p$ の倍数 → $a$ が $p$ の倍数であることを示す
4. $a = pc$ を代入して $b^2 = pc^2$ を導く
5. 同様に $b$ も $p$ の倍数 → $a, b$ は公約数 $p$ をもち、互いに素に矛盾
「$P \Rightarrow Q$」の形の命題を証明する場合、対偶証明法（$\lnot Q \Rightarrow \lnot P$ を示す）と 背理法（$P$ かつ $\lnot Q$ を仮定して矛盾を導く）は似ていますが、微妙に異なります。
対偶証明法では「$\lnot Q$ から $\lnot P$ を導く」のに対し、 背理法では「$P$ と $\lnot Q$ の両方を使って矛盾を導く」ことができます。 背理法のほうが使える条件が多い分、適用範囲が広いのです。
特に「$\sqrt{2}$ は無理数である」のような「$P \Rightarrow Q$」の形ではない命題（単独の命題）に対しては、 対偶証明法は使えず、背理法が自然な選択肢となります。
紀元前3世紀ごろ、ユークリッドは著書『原論』のなかで、 素数が無限に存在することを証明しました。 2000年以上前の証明が、今なお教科書に載るほど美しい論証です。
「素数は無限にある」── 直感的には当然に思えますが、 これを厳密に証明するにはどうすればよいでしょうか？ ここでも背理法が活躍します。
仮定：素数が有限個しかないと仮定する。 それらをすべて列挙して $p_1, p_2, p_3, \ldots, p_n$ とする。
Step 1：次の整数 $N$ を考える。
$$N = p_1 \times p_2 \times p_3 \times \cdots \times p_n + 1$$
つまり、$N$ は「すべての素数の積に1を足した数」です。
Step 2：$N$ の性質を調べる。
$N$ を素数 $p_i$（$i = 1, 2, \ldots, n$）のどれで割っても、余りは1です。 なぜなら、$p_1 \times p_2 \times \cdots \times p_n$ は $p_i$ で割り切れるので、 それに1を足した $N$ は $p_i$ で割ると1余るからです。
Step 3：矛盾を導く。
$N \geq 2$ なので、$N$ は素数であるか、あるいは素数の積に分解できます。 しかし $N$ はどの $p_i$ でも割り切れないので、 $N$ 自身が新しい素数であるか、$p_1, \ldots, p_n$ には含まれない素因数をもちます。 いずれにせよ、$p_1, \ldots, p_n$ 以外の素数が存在することになり、 「素数は $p_1, \ldots, p_n$ のみ」という仮定に矛盾します。
結論：素数が有限個であるという仮定は誤り。よって素数は無限に存在する。 $\square$
✕ 誤：「$N = p_1 p_2 \cdots p_n + 1$ はどの $p_i$ でも割れないから、$N$ は素数」
○ 正：「$N$ は素数であるか、または $p_1, \ldots, p_n$ に含まれない新しい素因数をもつ。 いずれにせよ、新しい素数が存在する」
たとえば $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30031 = 59 \times 509$ です。 $N$ 自体は素数ではありませんが、59と509という新しい素数が見つかります。 証明のポイントは「$N$ が素数かどうか」ではなく、「既知の素数リストにない素数が必ず存在する」ことです。
この証明の美しさは、「すべての素数を集めたつもりで、そこに含まれない素数を構成的に作り出す」点にあります。
$N = p_1 p_2 \cdots p_n + 1$ という数の構成が天才的です。 「すべての素数の積」を作ることで「どの素数でも割り切れない」性質を生み出し、 そこに1を足すことで $N \geq 2$ を保証します。
背理法の仮定「素数は有限個」が「すべての素数を列挙できる」という条件を与え、 その条件を使って矛盾を構成する。背理法の王道パターンです。
素数が無限にあることは証明されましたが、「素数がどのように分布しているか」は 数学最大の未解決問題の1つに関わります。 素数定理によれば、$x$ 以下の素数の個数はおよそ $\frac{x}{\ln x}$ 個です。
また、差が2の素数のペア（双子素数：3と5、11と13、17と19など）が無限にあるかどうかは、 「双子素数予想」として未解決です。 素数は無限にあるのに、双子素数が無限にあるかどうかはわからない。 条件が少し変わるだけで、問題の難しさが劇的に変わるのが数論の面白さです。
ここまで学んだ整数の証明手法を整理し、どの問題でどの手法を使うかの判断基準をまとめましょう。
| 手法 | 使う場面 | ポイント |
|---|---|---|
| 偶奇の場合分け | 偶数・奇数に関する性質の証明 | $n = 2k$ と $n = 2k+1$ の2パターン |
| $m$ で割った余りの分類 | $m$ の倍数であることの証明 | $n = mk, mk+1, \ldots, mk+(m-1)$ の $m$ パターン |
| 連続整数の性質 | 倍数の証明（因数分解できるとき） | 連続 $k$ 個の整数の積は $k!$ の倍数 |
| 背理法 | 「〜でない」「存在しない」の証明 | 結論の否定を仮定して矛盾を導く |
| 数学的帰納法 | 自然数に関する無限の命題の証明 | $n = 1$ で確認し、$n = k \Rightarrow n = k+1$ を示す |
整数の証明問題に出会ったとき、次の順序で手法を検討しましょう。
Q1. 整数 $n$ が奇数のとき、$n^2$ を4で割った余りは何ですか？
Q2. 「$n^2$ が3の倍数ならば $n$ も3の倍数」を証明するには、何で割った余りで場合分けしますか？
Q3. 背理法で「$\sqrt{2}$ は無理数」を証明するとき、最初に仮定することは何ですか？
Q4. 素数が無限に存在する証明で、$N = p_1 p_2 \cdots p_n + 1$ はなぜ素数とは限らないのですか？ 具体例を挙げてください。
Q5. 「$a$ が偶数、$b$ が奇数」を文字でおくとき、なぜ $a = 2k$、$b = 2k+1$ ではなく、$a = 2k$、$b = 2l+1$ と異なる文字を使うのですか？
この記事で学んだ内容を、入試形式の問題で確認しましょう。
$n$ を整数とする。$n^2 + 3n + 1$ は奇数であることを証明せよ。
(i) $n$ が偶数のとき：$n = 2k$ とおくと、$n^2 + 3n + 1 = 4k^2 + 6k + 1 = 2(2k^2 + 3k) + 1$。
$2k^2 + 3k$ は整数なので、$n^2 + 3n + 1$ は奇数。
(ii) $n$ が奇数のとき：$n = 2k+1$ とおくと、
$n^2 + 3n + 1 = (2k+1)^2 + 3(2k+1) + 1 = 4k^2 + 4k + 1 + 6k + 3 + 1 = 4k^2 + 10k + 5 = 2(2k^2 + 5k + 2) + 1$。
$2k^2 + 5k + 2$ は整数なので、$n^2 + 3n + 1$ は奇数。
(i)(ii)より、すべての整数 $n$ について $n^2 + 3n + 1$ は奇数。 $\square$
方針：「奇数であること」＝「$2 \times (\text{整数}) + 1$ の形」を示す。偶奇で場合分け。
別解として、$n^2 + 3n + 1 = n(n+3) + 1$ と変形する方法もあります。 $n$ と $n+3$ は偶奇が同じ（差が偶数だから）ので、$n(n+3)$ は常に偶数。よって $n(n+3) + 1$ は奇数です。
整数 $n$ について、$n^2$ を 8 で割った余りは $0, 1, 4$ のいずれかであることを証明せよ。
偶奇で場合分けする。
(i) $n$ が偶数のとき：$n = 2m$ とおくと $n^2 = 4m^2$。
$m$ が偶数なら $m = 2l$、$n^2 = 16l^2$ → 8で割った余りは $0$。
$m$ が奇数なら $m = 2l+1$、$n^2 = 4(4l^2 + 4l + 1) = 16l^2 + 16l + 4$ → 8で割った余りは $4$。
(ii) $n$ が奇数のとき：$n = 2m+1$ とおくと、
$n^2 = 4m^2 + 4m + 1 = 4m(m+1) + 1$。
$m$ と $m+1$ は連続整数なのでどちらかは偶数。よって $m(m+1)$ は偶数。$m(m+1) = 2s$ とおくと $n^2 = 8s + 1$。
8で割った余りは $1$。
(i)(ii)より、$n^2$ を8で割った余りは $0, 1, 4$ のいずれかである。 $\square$
方針：8パターン（$n = 8k, 8k+1, \ldots, 8k+7$）で場合分けしてもよいが、計算が大変。 偶奇→さらに偶奇、と段階的に分けるのが効率的。
この結果から、$8k + 2, 8k + 3, 8k + 5, 8k + 6, 8k + 7$ の形の整数は、どんな整数の2乗にもなれないことがわかります。
$\sqrt{3}$ が無理数であることを背理法を用いて証明せよ。
$\sqrt{3}$ が有理数であると仮定する。 互いに素な正の整数 $p, q$ を用いて $\sqrt{3} = \dfrac{p}{q}$ と表せる。
両辺を2乗すると $3 = \dfrac{p^2}{q^2}$、すなわち $p^2 = 3q^2$ ……①
①より $p^2$ は3の倍数。 $p$ が3の倍数でないとすると、$p = 3k+1$ または $p = 3k+2$ の形。 いずれの場合も $p^2$ を3で割った余りは1となり、$p^2$ が3の倍数であることに矛盾。 よって $p$ は3の倍数。$p = 3m$ とおく。
①に代入すると $9m^2 = 3q^2$、$q^2 = 3m^2$。 同様に $q$ も3の倍数。
$p, q$ がともに3の倍数なので互いに素に矛盾。 よって $\sqrt{3}$ は無理数である。 $\square$
方針：$\sqrt{2}$ の証明と同じ構造。 「$p^2$ が3の倍数 → $p$ も3の倍数」を示すために、余りの分類（Section 2）を使うのがポイント。
$a, b, c$ を整数とする。$a^2 + b^2 = c^2$ のとき、$a, b, c$ のうち少なくとも1つは偶数であることを証明せよ。
背理法で証明する。$a, b, c$ がすべて奇数であると仮定する。
奇数の2乗を4で割った余りは1であるから（Section 1 の公式より）、
$$a^2 \equiv 1 \pmod{4}, \quad b^2 \equiv 1 \pmod{4}$$
よって $a^2 + b^2 \equiv 1 + 1 = 2 \pmod{4}$
一方、$c$ が奇数なので $c^2 \equiv 1 \pmod{4}$。
$a^2 + b^2 \equiv 2 \pmod{4}$ と $c^2 \equiv 1 \pmod{4}$ は一致しない。
これは $a^2 + b^2 = c^2$ に矛盾する。
よって、$a, b, c$ がすべて奇数であることはありえず、少なくとも1つは偶数である。 $\square$
方針：「少なくとも1つは偶数」の否定は「すべて奇数」。背理法で「すべて奇数」を仮定し、 4で割った余りの矛盾を導く。これはピタゴラス数の偶奇分析の出発点でもある。
この結果は、ピタゴラスの三つ組 $(a, b, c)$ の性質を調べるための第一歩です。 さらに詳しく分析すると、$a, b$ がともに偶数で $c$ が奇数になることもありません （左辺が4の倍数、右辺の奇数の2乗は4で割って1余るため矛盾）。