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

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

ユークリッド

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

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

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

素数の個数が有限と仮定し、

p 1, \dots p n

が素数の全てとする。その積

P = p 1 \times \dots \times p n

に

1

を加えた数

P + 1

は、

p 1, \dots, p n

のいずれでも割り切れないので、素数でなければならない。しかし、これは

p 1, \dots, p n

が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無限に存在する。

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

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

ゴールドバッハ

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

F_{n}=2^{2^{n}}+1

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

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

F_{0}F_{1}\cdots F_{m}=F_{m+1}-2

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

オイラー

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

素数は有限個の $p 1, \dots, p n$ からなると仮定する。各素数 $p i$ に対し、等比級数の公式により

{\frac {1}{1-{p_{i}}^{-1}}}=\sum _{k=0}^{\infty }{\frac {1}{{p_{i}}^{k}}}

が成り立つ。 $i = 1, \dots, 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年に発表した、より簡潔な証明である^[6]。

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

\sum _{i=k+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {1}{2}}

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

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

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

と表せるから、

N_{1}\leq \sum _{i=k+1}^{\infty }\left\lfloor {\frac {N}{p_{i}}}\right\rfloor \leq \sum _{i=k+1}^{\infty }{\frac {N}{p_{i}}}<{\frac {N}{2}}

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

N_{2}\leq 2^{k}{\sqrt {N}}

を得る。よって、

N=N_{1}+N_{2}<{\frac {N}{2}}+2^{k}{\sqrt {N}}

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

フュルステンベルグ

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

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

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

（ただし、 $a, b$ は整数で、 $a \neq 0$ ）全体を開基とする位相を定める。換言すれば、この位相における開集合は、（空集合であるか）任意個の無限等差数列の和集合である。このとき、空でない有限集合は開集合ではないことに注意する。

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

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

という表示により、閉集合でもある。 $p 1, \dots, p n$ が素数全体と仮定すると、

A:=\bigcup _{i=1}^{n}p_{i}\mathbb {Z}

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

$π$ が無理数であることを使った証明

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

{\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 \;

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

サイダック

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

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

脚注

^ 成立当初の原論には本定理が書かれておらず、本定理の記述は後から追加されたものである可能性がある。参考: エウクレイデス全集第2巻、齋藤憲訳、東京大学出版会、pp. 39, 263、2015
^ D. E. Joyce による英語訳。日本語訳には中村幸四郎らによる訳がある。
^ Hardy and Woodgold, p. 44
^ ^a ^b ^c Ribenboim, 第1章
^ C. K. Caldwell, Goldbach's Proof of the Infinitude of Primes (1730) - Prime Pages
^ ^a ^b ^c Aigner and Ziegler, 第1章
^ Debnath, Lokenath (2010), The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientific, p. 214, ISBN 9781848165267 .
^ Saidak, Filip (2006), “A new proof of Euclid's theorem”, Amer. Math. Monthly 113: 937–938, doi:10.2307/27642094, MR2271540, Zbl 1228.11011
^ C. K. Caldwell, Filip Saidak's Proof - Prime Pages

参考文献

中村幸四郎他訳『ユークリッド原論』共立出版、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.

外部リンク

Weisstein, Eric W. "Euclid's Theorems". mathworld.wolfram.com (英語).
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

[1] 成立当初の原論には本定理が書かれておらず、本定理の記述は後から追加されたものである可能性がある。参考: エウクレイデス全集第2巻、齋藤憲訳、東京大学出版会、pp. 39, 263、2015

[2] D. E. Joyce による英語訳。日本語訳には中村幸四郎らによる訳がある。

[3] Hardy and Woodgold, p. 44

[riben-4] Ribenboim, 第1章

[5] C. K. Caldwell, Goldbach's Proof of the Infinitude of Primes (1730) - Prime Pages

[erdos-6] Aigner and Ziegler, 第1章

[7] Debnath, Lokenath (2010), The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientific, p. 214, ISBN 9781848165267 .

[8] Saidak, Filip (2006), “A new proof of Euclid's theorem”, Amer. Math. Monthly 113: 937–938, doi:10.2307/27642094, MR2271540, Zbl 1228.11011

[9] C. K. Caldwell, Filip Saidak's Proof - Prime Pages

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]