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

である。これを展開すると、各項は \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 のみであること(この証明での仮定)から、任意の自然数は \prod_{i=1}^n p_i^k_i} (各 k_i は0以上の整数)と表せる。したがって、任意の自然数 m について、上記の M の総和表現の中に \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 > 1, b >1 によって n = ab と表せる。a, bn より小さいので、ともに素数の積で表せる。するとそれらの積である n も素数の積で表せることになり矛盾する。
以上よりこのような n は存在せず、任意の自然数は素数の積として表せる。
※リンク先のWikipediaは算術の基本定理のページであり、この定理では各自然数に対して素数の積(素因数分解)が1通りしかないことも証明しているが、素数が無限に存在することの証明にはそこまでは必要ない。

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

任意の自然数nが素数の積として表せることを証明する。
(1) n = 1, 2 のときは明らかに成り立つ。
(2) n = 1, 2, \ldots, k - 1 \, (k > 2) で成り立つとする。
k が素数なら、それ自身が素数の積であるから n = k でも成り立つ。
k が合成数なら、kk より小さい自然数の積で表すことができ、仮定よりそれらは素数の積で表せるから、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 = 1 + \sum_{i=1}^\infty {\sum_{j=2^{i-1}+1}^{2^i}\frac{1}{j}}
\displaystyle >1 + \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 = 1 + \sum_{i=1}^\infty \frac{1}{2}

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

はてなブックマーク - 素数が無限に存在することの証明 (4)
[`evernote` not found]

コメントを残す

メールアドレスが公開されることはありません。