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

**素数が無数に存在することの証明**（そすうがむすうにそんざいすることのしょうめい）は、古くは紀元前3世紀頃のユークリッドの『原論』に記され、その後も多くの証明が与えられている。素数が無数に存在することは、しばしば**ユークリッドの定理**（ユークリッドのていり、）と呼ばれる。

## ユークリッド
『原論』第9巻命題20で、素数が無数に存在することが示されている。その証明は、次の通りである。なお「任意」は誤訳と思われる。

この証明は、しばしば次のような背理法の形で表現される。
:素数の個数が有限と仮定し、 が素数の全てとする。その積  に  を加えた数  は、 のいずれでも割り切れないので、素数でなければならない。しかし、これは  が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無限に存在する。
この形の証明のために、「ユークリッドは、背理法で素数が無数にあることを証明した」「ユークリッドの証明は、存在のみを示しており、具体的な構成の手続きを示していない」「ユークリッドは、最初のいくつかの素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、いずれも正しくない。『原論』の証明は背理法ではなく、であるによるものである。また、最後の主張は「 2 &times; 3 &times; 5 &times; 7 &times; 11 &times; 13 + 1 = 59 &times; 509 = 30,031 」という反例により、歴史的にのみならず数学的にも誤りである。

1878年、クンマーは、 の代わりに  を考えても、同様に証明できることを注意した。

## ゴールドバッハ
ゴールドバッハは、1730年7月にオイラーに宛てた手紙の中で、フェルマー数
:F_n =2^{2^n} +1
を利用して、素数が無数にあることを証明している。

フェルマー数たちが互いに素であることが示されれば、無数にあるフェルマー数の素因子を考えることにより、無数に素数を得る。実際、 に関する数学的帰納法により、簡単に
:F_0 F_1 \cdots F_m =F_{m+1} -2
が得られるので、ある素数  が2つのフェルマー数を割り切るとすると、 は  も割り切ることになって不合理である。

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

素数は有限個の  からなると仮定する。各素数  に対し、等比級数の公式により
:\frac{1}{1-{p_i}^{-1}} =\sum_{k=0}^\infty \frac{1} =\prod_{i=1}^n \sum_{k=0}^\infty \frac{1}{{p_i}^k} =\sum_{m=1}^\infty \frac{1}{m}
を得る。左辺は有限値であるのに対し、右辺は調和級数であり、発散するので、矛盾する。

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

素数の逆数和は収束すると仮定する。 番目の素数を  で表すことにすると、ある番号  が存在して
:\sum_{i=k+1}^\infty \frac{1}{p_i}
である。素数全体を2つのグループに分け、 を「小さい」素数、 以降を「大きい」素数と呼ぶことにする。 以下の自然数で、「大きい」素数で割れる数と、「小さい」素数でしか割れない数に分け、前者の個数を 、後者の個数を  とおく。当然  である。

以下、 と  の大きさを見積もる。 以下の  の倍数の個数は、床関数を用いて
:\left\lfloor \frac{N}{p} \right\rfloor
と表せるから、
:N_1 \le \sum_{i=k+1}^\infty \left\lfloor \frac{N}{p_i} \right\rfloor \le \sum_{i=k+1}^\infty \frac{N}{p_i}
を得る。ここに、最後の不等号は上記の仮定から従う。次に、 を小さい素数でしか割れない  以下の自然数とし、（ は平方因子を含まない） と表す。 の可能性は高々 2 通りであり、 であるから、
:N_2 \le 2^k \sqrt{N}
を得る。よって、
:N=N_1 +N_2 
となる。しかし、この式は  に対して成り立たない。

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

整数全体からなる集合  に、両方向への無限等差数列
:a\mathbb{Z}+b=\{ax+b \mid x \in \mathbb{Z}\}
（ただし、 は整数で、）全体を開基とする位相を定める。換言すれば、この位相における開集合は、（空集合であるか）任意個の無限等差数列の和集合である。このとき、空でない有限集合は開集合ではないことに注意する。

任意の無限等差数列は、開集合であると同時に、
:a\mathbb{Z}+b=\Z \setminus \left( \bigcup_{i=1}^{a-1} (a\mathbb{Z}+b+i) \right)
という表示により、閉集合でもある。 が素数全体と仮定すると、
:A:=\bigcup_{i=1}^n p_i\mathbb{Z}
は有限個の閉集合の和集合であるから閉集合である。したがって閉集合  の補集合  は開集合である。ところが  以外の任意の整数は何らかの素数で割り切れるから、 である。これは空でない有限集合であるため開集合ではなく、矛盾が生じる。

## '''' が無理数であることを使った証明

ライプニッツの公式をオイラー積の形で表すと
: \frac{\pi}{4} = \frac{3}{4} \times \frac{5}{4} \times \frac{7}{8} \times \frac{11}{12} \times \frac{13}{12} \times \frac{17}{16} \times \frac{19}{20} \times \frac{23}{24} \times \frac{29}{28} \times \frac{31}{32} \times \cdots \; 
この積の分子は奇素数であり、分母はそれぞれに対応する分子に一番近い  の倍数である。もし素数が有限個ならば **' は有理数として表すことができる。しかし **' は無理数なので、背理法より素数は無限に存在する。

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

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

## 脚注

## 参考文献
* 中村幸四郎他訳『ユークリッド原論』共立出版、1996年 ISBN 978-4320015135
* M. Aigner and G. M. Ziegler, *Proofs from the Book*, 3rd edition, Springer, 2003. ISBN 978-3540404606
** 蟹江幸博訳『天書の証明』シュプリンガー・フェアラーク東京、2002年（2nd edition の訳）ISBN 978-4431709862
* Paulo Ribenboim, *The Book of Prime Number Records*, Springer, 1988 ISBN 978-0387965734
** 吾郷孝視訳『素数の世界』共立出版、1995年 ISBN 978-4320014848
* G. H. Hardy and E. M. Wright, *An Introduction to the Theory of Numbers*, Fifth Edition, Oxford University Press, 1980 ISBN 978-0198531715
** 示野信一、矢神毅訳『数論入門Ⅰ』シュプリンガー・フェアラーク東京、2001年 ISBN 978-4431708483
* M. Hardy and C. Woodgold, ''Prime Simplicity'', Mathematical Intelligencer, volume 31, number 4, 2009, 44-52.

## 関連項目
* 素数階乗素数
* 素数定理

## 外部リンク
* 
*  C. K. Caldwell Proofs that there are infinitely many primes - Prime Pages.
* R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.-2012) and another new proof, Arxiv preprint arXiv:1202.3670, 2012