第2章 背理法

証明（背理法）

Step 1：背理法の仮定を置く。

$\sqrt{2}$ が有理数であると仮定する。

Step 2：仮定を式で表す。

有理数の定義より、互いに素な整数 $p, q$（$q \neq 0$）を用いて

$$\sqrt{2} = \dfrac{p}{q}$$

と書ける（既約分数で表せる）。

Step 3：両辺を2乗する。

$$2 = \dfrac{p^2}{q^2}$$

両辺に $q^2$ を掛けて整理すると

$$p^2 = 2q^2 \quad \cdots (*)$$

Step 4：$p$ が偶数であることを示す。

$(*)$ より $p^2 = 2q^2$ なので、$p^2$ は偶数である。

ここで補題を使う：「$n^2$ が偶数ならば $n$ は偶数」（後述）

よって $p$ は偶数であり、ある整数 $k$ を用いて

$$p = 2k$$

と書ける。

Step 5：$q$ も偶数であることを示す。

$p = 2k$ を $(*)$ に代入する：

\begin{align} (2k)^2 &= 2q^2 \\ 4k^2 &= 2q^2 \\ 2k^2 &= q^2 \end{align}

よって $q^2$ は偶数なので、$q$ も偶数である。

Step 6：矛盾を指摘する。

$p$ も $q$ も偶数であることがわかった。

しかしこれは「$p$ と $q$ は互いに素」という Step 2 の仮定に矛盾する。

（$p$ と $q$ がともに偶数なら、公約数 $2$ を持つ）

Step 7：結論を述べる。

矛盾が生じたので、最初の仮定「$\sqrt{2}$ が有理数」は誤りである。

よって $\sqrt{2}$ は無理数である。$\square$

補題の証明（対偶）

対偶「$n$ が奇数ならば $n^2$ は奇数」を示す。

$n$ を奇数とすると、ある整数 $m$ を用いて $n = 2m + 1$ と書ける。

\begin{align} n^2 &= (2m + 1)^2 \\ &= 4m^2 + 4m + 1 \\ &= 2(2m^2 + 2m) + 1 \end{align}

$2m^2 + 2m$ は整数なので、$n^2$ は奇数である。

対偶が真なので、元の命題も真。$\square$

証明（背理法）

Step 1：背理法の仮定。

素数が有限個しかないと仮定する。

すべての素数を $p_1, p_2, \ldots, p_n$ とする。

Step 2：新しい数を構成する。

次の数 $N$ を考える：

$$N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$$

（すべての素数の積に $1$ を足した数）

Step 3：$N$ の性質を調べる。

$N > 1$ なので、$N$ は素数であるか、または素因数を持つ。

Step 4：矛盾を導く。

任意の素数 $p_i$（$i = 1, 2, \ldots, n$）について：

$$N = p_1 p_2 \cdots p_n + 1$$

を $p_i$ で割ると、$p_1 p_2 \cdots p_n$ は $p_i$ で割り切れるから

$$N \equiv 1 \pmod{p_i}$$

つまり $N$ を $p_i$ で割ると余り $1$ となる。

よって $N$ はどの $p_i$ でも割り切れない。

Step 5：矛盾を指摘する。

$N > 1$ なのに、$N$ はどの素数でも割り切れない。

これは「$1$ より大きい整数は素因数を持つ」という事実に矛盾する。

（$N$ 自身が新しい素数であるか、リストにない素因数を持つ）

Step 6：結論。

矛盾が生じたので、「素数が有限個」という仮定は誤り。

よって素数は無限に存在する。$\square$