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

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

1. ユークリッド
---------

『原論』第9巻命題20で、素数が無数に存在することが示されている。その証明は、次の通りである。 この証明は、しばしば次のような背理法の形で表現される。

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

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

2. ゴールドバッハ
----------

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

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

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

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

3. オイラー
-------

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

素数は有限個の //p//sub からなると仮定する。各素数 psub に対し、等比級数の公式により

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

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

4. エルデシュ
--------

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

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

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

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

と表せるから、

を得る。ここに、最後の不等号は上記の仮定から従う。次に、x}} を小さい素数でしか割れない N}} 以下の自然数とし、//x// =}} //uv//sup と表す。u}} の可能性は高々 2//k//}} 通りであり、//v//sup であるから、

を得る。よって、

となる。しかし、この式は //N// =}} 2sup に対して成り立たない。

5. フュルステンベルグ
------------

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

整数全体からなる集合 Z}} に、両方向への無限等差数列

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

任意の無限等差数列は、開集合であると同時に、

という表示により、閉集合でもある。//p//sub が素数全体と仮定すると、

は有限個の閉集合の和集合であるから閉集合である。したがって閉集合 A}} の補集合 1=//Asup は開集合である。ところが ±1}} 以外の任意の整数は何らかの素数で割り切れるから、1=//Asup である。これは空でない有限集合であるため開集合ではなく、矛盾が生じる。

6. //π}}// が無理数であることを使った証明
--------------------------

ライプニッツの公式をオイラー積の形で表すと

この積の分子は奇素数であり、分母はそれぞれに対応する分子に一番近い 4}} の倍数である。もし素数が有限個ならば //// は有理数として表すことができる。しかし //// は無理数なので、背理法より素数は無限に存在する。

7. サイダック
--------

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

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

8. 脚注
-----

9. 参考文献
-------

中村幸四郎他訳『ユークリッド原論』共立出版、1996年 ISBN 978-4320015135
M. Aigner and G. M. Ziegler, //Proofs from the Book//, 3rd edition, Springer, 2003. ISBN 978-3540404606
蟹江幸博訳『天書の証明』シュプリンガー・フェアラーク東京、2002年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, [1], Mathematical Intelligencer, volume 31, number 4, 2009, 44-52.

10. 関連項目
--------

素数階乗素数
素数定理

11. 外部リンク
---------

C. K. Caldwell [2] - Prime Pages.
R. Mestrovic, Euclid's theorem on the infinitude of primes: a historical survey of its proofs  and another new proof, Arxiv preprint [3], 2012