素数の無限性の証明 : Proofs of The Infinitude of Primes

Theorem(Euclid). There are infinitely many prime numbers.

人類たるもの知っておくべき事実でしょう。この記事では、上の定理の証明を高校数学の範囲内*1で、できるだけ多く紹介しようと思います。

素数の無限性の証明は、大きく次の2つに分けられます。

素数を有限と仮定して矛盾を導く。
互いに素な組を無限に生成する。

注意

細かな定理、補題の証明は省きます。
$\mathbb{N}$ は自然数全体の集合、 $\mathbb{P}$ は素数全体の集合、 $p_n$ は $n$ 番目の素数、 $P$ は素数の総積とします。

証明

Proof 1. $q_1, q_2, q_3, \cdots, q_n$ を異なる $n$ 個の素数とする。 $n$ によらず、新しい素数 $q_{n+1}$ を生成出来れば証明は完了する。ところで $N := q_1 q_2 q_3 \cdots q_n + 1$ は $q_i (1 \leq i \leq n)$ で割り切れない。 $2$ 以上の自然数は素因数分解可能なので、 $N$ は素因数 $q_{n+1}$ を持つ。□

Proof 2. 素数を有限個と仮定する。 $P + 1$ は如何なる素数でも割り切れない。これは $2$ 以上の自然数は素因数分解可能であることに矛盾する。□

Proof 3. 任意の正整数 $n_1$ につき、 $n_1 (n_1 + 1)$ をとる。このとき、 $n_1$ と $n_1 + 1$ は互いに素なので、 $n_1$ の素因数の集合は、 $n_1 (n_1 + 1)$ の素因数の集合の真部分集合である。 $n_2 = n_1 (n_1 + 1), n_3 = n_2 (n_2 + 1), \cdots$ と定めることによって、同様の議論を無限回繰り返すことができる。□

Proof 4. 非負整数 $n$ について、 $F_n := 2^{2^n} + 1$ と定める。任意の正整数 $n$ について、等式

$F_n - 2 = F_1 F_2 F_3 \cdots F_{n-1}$

が成り立つ。これは数学的帰納法より簡単に示せる。 $m < n$ を満たす正整数 $m$ につき、 $F_n$ と $F_m$ の最大公約数を $d$ とする。上の等式より、 $F_n - F_1 F_2 F_3 \cdots F_{n-1} = 2$ は $d$ で割り切れるが、 $F_n$ は定義式より奇数である。よって $d = 1$ であり、 $F_1, F_2, F_3, \cdots, F_{n-1}$ はどの $2$ つを取っても互いに素である。□

Proof 5. 素数を有限個と仮定する（その個数を $n$ とする）。 $N > P$ を満たすような $N$ を任意に取る。このとき、 $N$ 以下の素数の2乗で割り切れない数は $2^n$ 個（ $P$ の約数の個数と考えれば良い）。 $N$ 以下の素数の2乗で割り切れる数は多くとも $\sum_{i=1}^n N / p_i^2$ 個である。よって、 $\delta > 0$ を用いて

$\displaystyle N \leq 2^n + \sum_{i=1}^n \frac{N}{p_i^2} < 2^n + N \sum_{k=2}^{\infty} \frac{1}{k^2} = 2^n + N (\sum_{k=1}^{\infty} \frac{1}{k^2} - 1) = 2^n + N(1 - \delta) \left( \because \sum_{k=1}^{\infty} \frac{1}{k^2} < 2 \right)$

従って、 $N \delta < 2^n$ であるがこれは十分大きい $N$ を取れば成り立たない。□

Proof 6. 素数を有限個と仮定する。 $p$ をある素数とする。このとき

$\displaystyle 0 < \sin \left( \frac{\pi}{p} \right) = \sin (\pi \frac{1 + 2P}{p}) = 0$

がとある $p$ で成り立つ。□

Proof 7. 素数を有限個と仮定する。素数 $p$ が正整数 $n$ を割り切る回数を $v_p(n)$ で表す。Legendreの公式より、

$\displaystyle v_p(n!) = \sum_{i=1}^{\infty} \left[ \frac{n}{p^i} \right] \leq \sum_{i=1}^{\infty} \frac{n}{p^i} = \frac{n}{p-1} < n$

$\displaystyle n! = \prod_{p:prime} p^{v_p(n!)} < \prod_{p:prime} p^n = P^n$

である。しかしこれは十分大きい $n$ で成り立たない。□

Proof 8. 任意の自然数 $N (\geq 2)$ に対して、 $N$ 以下の素数の個数を $n$ とする。 $P = p_1^{e_1} p_2^{e_2} \cdots p_n^{e_n} (e_i \geq 1)$ と定める。また $P = \delta_1 \delta_2 (\delta_1 \leq \delta_2)$ を満たすような、互いに素な自然数 $\delta_1, \delta_2$ を取り $Q = \delta_2 - \delta_1$ と定める。ここで、 $Q$ は $N$ 以下の素数では割り切れないから、 $N$ 以上の素数の積である。□

Proof 9. ゼータ関数のEuler積表示より、

$\displaystyle \sum_{k=1}^{\infty} \frac{1}{k} = \prod_{p:prime} \frac{1}{1-p^{-1}}$

である。左辺は調和級数となり発散する。よって右辺は無限積。□

Proof 10. $F(n)$ を $n$ の素因数の個数とする。素数を有限個と仮定すれば、 $F(n)$ は周期 $P$ の周期数列であるが、 $F(n) = 0 \Leftrightarrow n = 1$ より矛盾である。□

Proof 11. 素数を有限個と仮定する（その個数を $n ( \geq 2)$ とする）。 $P = p_2 p_3 \cdots p_n = 3 p_3 \cdots p_n$ とすれば $P - 2$ は $P$ と互いに素であり、奇数の素因数を持たない。しかし、 $P -2$ は奇数だから、 $P = 3$ 。すなわちこの世に素数は $2, 3$ のみである。□