素数が無数に存在することの証明

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

素数が無数に存在することの証明は、古くは紀元前3世紀頃のユークリッドの『原論』に記され、その後も多くの証明が与えられている。素数が無数に存在することは、しばしばユークリッドの定理: Euclid's theorem)と呼ばれる。

ユークリッド[編集]

『原論』第9巻命題20で、素数が無数に存在することが示されている。その証明は、次の通りである[1]

a, b, …, k を任意に与えられた素数のリストとする。その積 P := a × b × … × k に 1 を加えた数 P + 1 は、素数であるか、素数でないかのいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 p で割り切れるが、p はやはり最初のリストに含まれない。なぜならば、リスト中の素数は P を割り切るので、P + 1 を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。

この証明は、しばしば次のような形で表現される。

素数の個数が有限と仮定し、p1, … pn が素数の全てとする。その積 P = p1 × … × pn に 1 を加えた数 P + 1 は、p1, …, pn のいずれでも割り切れないので、素数でなければならない。しかし、これは p1, …, pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無数に存在する。

この形の証明のために、「ユークリッドは、背理法で素数が無数にあることを証明した」「ユークリッドの証明は、存在のみを示しており、具体的な構成の手続きを示していない」「ユークリッドは、最初のいくつかの素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、いずれも正しくない[2]。特に、最後の主張は 2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 という反例により、歴史的にのみならず数学的に誤りである。

1878年、クンマーは、P + 1 の代わりに P - 1 を考えても、同様に証明できることを注意した[3]

ゴールドバッハ[編集]

ゴールドバッハは、1730年7月にオイラーに宛てた手紙の中で、フェルマー数

F_n=2^{2^n}+1

を利用して、素数が無数にあることを証明している[4]

フェルマー数たちが互いに素であることが示されれば、無数にあるフェルマー数の素因子を考えることにより、無数に素数を得る。実際、m に関する数学的帰納法により、簡単に

F_0F_1 \cdots F_m=F_{m+1}-2

が得られるので、ある素数 p がふたつのフェルマー数を割り切るとすると、p は 2 も割り切ることになって不合理である。

オイラー[編集]

オイラーによる証明[3][5]は、リーマンゼータ関数オイラー積表示を用いたものである。

素数は有限個の p1, …, pn からなると仮定する。各素数 pi に対し、等比級数の公式により

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

が成り立つ。i = 1, …, n における両辺の総乗を取ると、任意の自然数は素数の積として一意に表せる(算術の基本定理)ことより、

\prod_{i=1}^n \frac{1}{1-p_i^{-1}} =\prod_{i=1}^n \sum_{k=0}^\infty \frac{1}{{p_i}^k} =\sum_{m=1}^\infty \frac{1}{m}

を得る。左辺は有限値であるのに対し、右辺は調和級数であり、発散するので、矛盾する。

エルデシュ[編集]

素数の逆数和は(無限大に)発散することが示されば、素数は無数に存在することが直ちに従う。素数の逆数和が発散することは、オイラーが初めて証明したが、以下はエルデシュが1938年に発表した、より簡潔な証明である[5]

n 番目の素数を pn で表す。素数の逆数和は収束すると仮定すると、ある番号 k が存在して

\sum_{i=k+1}^\infty \frac{1}{p_i}<\frac{1}{2}

である。素数全体を2つのグループに分け、p1, …, pk を「小さい」素数、pk+1 以降を「大きい」素数と呼ぶことにする。N 以下の自然数で、「大きい」素数で割れる数と、「小さい」素数でしか割れない数に分け、前者の個数を N1、後者の個数を N2 とおく。当然 N = N1 + N2 である。

以下、N1N2 の大きさを見積もる。N 以下の p の倍数の個数は、床関数を用いて

\left\lfloor \frac{N}{p} \right\rfloor

と表せるから、

N_1=\sum_{i=k+1}^\infty \left\lfloor \frac{N}{p_i} \right\rfloor \le \sum_{i=k+1}^\infty \frac{N}{p_i}<\frac{N}{2}

を得る。ここに、最後の不等号は上記の仮定から従う。次に、x を小さい素数でしか割れない N 以下の自然数とし、x = uv2 と表す。ただし、u は平方因子を含まないとする。u の可能性は高々 2k 通りであり、v2xN であるから、

N_2 \le 2^k\sqrt{N}

を得る。よって、

N=N_1 +N_2 <\frac{N}{2} +2^k \sqrt{N}

となる。しかし、この式は N = 22k+2 に対して成り立たない。

フュルステンベルグ[編集]

フュルステンベルグの証明は、トポロジーを用いたものである[3][5]。彼は、まだ学部生であった1955年に、証明を発表した。

整数の集合 Z に、両方向への無限等差数列

a\mathbb{Z}+b=\{ax+b\,|\,x \in \mathbb{Z}\}

全体を開基とする位相を定める。換言すれば、この位相における開集合は、空集合であるか、あるいは任意個の無限等差数列の和集合である。任意の無限等差数列は、開集合であると同時に、

a\mathbb{Z}+b=\Z \setminus \left( \bigcup_{i=1}^{a-1} (a\mathbb{Z}+b+i) \right)

という表示により、閉集合でもある。p1, …, pn が素数の全てと仮定すると、有限個の閉集合の和集合

A:=\bigcup_{i=1}^n p_i\mathbb{Z}

は閉集合である。±1 以外の任意の整数は何らかの素数で割り切れるから、A補集合は {±1} である。閉集合の補集合だから開集合であるはずだが、空集合でも無限等差数列の和集合でもないから、不合理である。

現代[編集]

現代においても、新たな証明が次々に提案されている。その中でも、2006年に発表されたフィリップ・サイダックによる証明は非常に簡潔である[6]

n は2以上の整数とする。nn + 1 は互いに素なので、N2 := n (n + 1) は少なくとも2つの異なる素因子を持つ。同様に、N2N2 + 1 は互いに素なので、N3 := N2 (N2 + 1) は少なくとも3つの異なる素因子を持つ。この操作を続けることにより、任意に多くの異なる素因子を持つ数を構成することができるので、素数は無数に存在する。

脚注[編集]

  1. ^ D. E. Joyce による英語訳。日本語訳には中村幸四郎らによる訳がある。
  2. ^ Hardy and Woodgold, p. 44
  3. ^ a b c Ribenboim, 第1章
  4. ^ C. K. Caldwell, Goldbach's Proof of the Infinitude of Primes (1730) - Prime Pages
  5. ^ a b c Aigner and Ziegler, 第1章
  6. ^ C. K. Caldwell, Filip Saidak's Proof - Prime Pages

参考文献[編集]

関連項目[編集]

外部リンク[編集]