全脳科学帳

これを好む者はこれを楽しむ者に如かず

素数が無限に存在することの証明 (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

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

最後の総和は無限大に発散するから、調和級数も無限大に発散する。