素数が無限に存在することの証明 (4)

次に紹介するのは、かのレオンハルト・オイラーによる証明。これはかなり毛色が異なる。

証明
素数が有限の $n$ 個しか存在しないと仮定し、それらを $p_1, p_2, \ldots, p_n$ とする。各素数 $p_i$ に対し、等比数列の和の公式より

$\displaystyle \sum_{k=0}^\infty \frac{1}{p_i^k} = \frac{1}{1 - \frac{1}{p_i}}$

である。右辺を $p_1, p_2, \ldots, p_n$ のすべてについて掛け合わせた値

$\displaystyle M = \prod_{i=1}^n {\frac{1}{1 - \frac{1}{p_i}}}$

を考えると、これは有限の値の有限個の積であるから、 $M$ は有限の値である。一方、左辺の等比数列の和の方を使って表すと

$\displaystyle M = \prod_{i=1}^n {\sum_{k=0}^\infty \frac{1}{p_i^k}}$

$\displaystyle = \Bigl(1 + \frac{1}{p_1} + \frac{1}{p_1^2} + \cdots\Bigr)\Bigl(1 + \frac{1}{p_2} + \frac{1}{p_2^2} + \cdots\Bigr) \ldots\Bigl(1 + \frac{1}{p_n} + \frac{1}{p_n^2} + \cdots\Bigr)$

である。これを展開すると、各項は $\displaystyle \frac{1}{p_1}, \frac{1}{p_2}, \ldots, \frac{1}{p_n}$ の0乗以上を掛け合わせたものとなり、そのすべての組み合わせが現れる。すなわち

$\displaystyle M = \sum_{k_i} \frac{1}{\prod_{i=1}^n p_i^{k_i}}$

ただしこれは、0以上の整数値をとる数列 $k_i \, (0 \le i \le n)$ のすべての組み合わせにわたって和をとることを意味する。

任意の自然数は素数の積として表せる(証明は後述。ここで1は素数の0乗の積と見なす)ことと、素数は $p_1, p_2, \ldots, p_n$ のみであること(この証明での仮定)から、任意の自然数は $\displaystyle \prod_{i=1}^n p_i^{k_i}$ (各 $k_i$ は0以上の整数)と表せる。したがって、任意の自然数 $m$ について、上記の $M$ の総和表現の中に $\displaystyle \frac{1}{m}$ が現れる。よって

$\displaystyle M \ge \sum_{k=1}^\infty \frac{1}{k} = 1 + \frac{1}{2} + \frac{1}{3} +\frac{1}{4} + \cdots$

右辺は調和級数であり、無限大に発散する(証明は後述)。したがって $M$ は無限大に発散する。これは $M$ が有限の値であることと矛盾する。

以上より、素数が有限個しか存在しないという仮定が誤りであり、素数は無限に存在する。(証明終)

無限数列の積を使うので直感的に理解するのが少し難しいし、これで厳密に示せているのか不安になるが、素因数分解や調和級数と結びつけているのはおもしろい。

これを背理法を使わずに証明するにはどうするか? 単に、 $n$ 個の素数 $p_1, p_2, \ldots, p_n$ をとったときに $M$ は有限の値になるから調和級数と同じにはならず、すべての自然数を分母にするには任意の $n$ より大きな個数の素数が必要になることを言えばいいだけか。

上記の証明で、「任意の自然数が素数の積として表せること」と、「調和級数が無限大に発散すること」を使っている。これらの証明を書いておく。

任意の自然数が素数の積として表せることの証明(Wikipediaより)
素数の積として表せない自然数が存在するとし、そのような最小の数を $n$ とする。1は素数の0乗として表せ、素数はそれ自身で素数の積になっているので、 $n$ は合成数である。したがってある自然数 $a \gt 1, b \gt1$ によって $n = ab$ と表せる。 $a, b$ は $n$ より小さいので、ともに素数の積で表せる。するとそれらの積である $n$ も素数の積で表せることになり矛盾する。以上よりこのような $n$ は存在せず、任意の自然数は素数の積として表せる。 ※リンク先のWikipediaは算術の基本定理のページであり、この定理では各自然数に対して素数の積(素因数分解)が1通りしかないことも証明しているが、素数が無限に存在することの証明にはそこまでは必要ない。

これを背理法を使わずに証明するには? たとえば数学的帰納法で以下のようにやればいいと思う。

任意の自然数 $n$ が素数の積として表せることを証明する。

(1) $n = 1, 2$ のときは明らかに成り立つ。
(2) $n = 1, 2, \ldots, k - 1 \, (k \gt 2)$ で成り立つとする。
$k$ が素数なら、それ自身が素数の積であるから $n = k$ でも成り立つ。
$k$ が合成数なら、 $k$ は $k$ より小さい自然数の積で表すことができ、仮定よりそれらは素数の積で表せるから、 $k$ も素数の積で表すことができる。したがって、 $n = k$ でも成り立つ。
以上より、任意の自然数 $n$ は素数の積として表せる。

調和級数が無限大に発散することの証明
調和級数の分母の自然数を2の累乗で区切って表せば

$\displaystyle \sum_{k=1}^\infty \frac{1}{k} = 1 +\Bigl(\frac{1}{2}\Bigr) +\Bigl(\frac{1}{3} + \frac{1}{4}\Bigr) +\Bigl(\frac{1}{5} + \frac{1}{6} +\frac{1}{7} +\frac{1}{8}\Bigr) + \cdots$

$\displaystyle = 1 + \sum_{i=1}^\infty {\sum_{j=2^{i-1}+1}^{2^i}\frac{1}{j}}$

$\displaystyle \gt1 + \sum_{i=1}^\infty {\sum_{j=2^{i-1}+1}^{2^i}\frac{1}{2^i}} = 1 +\Bigl(\frac{1}{2}\Bigr) +\Bigl(\frac{1}{4} + \frac{1}{4}\Bigr) +\Bigl(\frac{1}{8} + \frac{1}{8} +\frac{1}{8} +\frac{1}{8}\Bigr) \cdots$