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

素数が無数に存在することの証明（そすうがむすうにそんざいすることのしょうめい）は、古くは紀元前3世紀頃のユークリッドの『原論』に記され、その後も多くの証明が与えられている。素数が無数に存在することは、しばしばユークリッドの定理（ユークリッドのていり、英: Euclid's theorem）と呼ばれる。 『原論』第9巻命題20で、素数が無数に存在することが示されている。その証明は、次の通りである。 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 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 = 30,031 」という反例により、歴史的にのみならず数学的にも誤りである。 1878年、クンマーは、P + 1 の代わりに P − 1 を考えても、同様に証明できることを注意した。 ゴールドバッハは、1730年7月にオイラーに宛てた手紙の中で、フェルマー数 F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{n}}+1} を利用して、素数が無数にあることを証明している。 フェルマー数たちが互いに素であることが示されれば、無数にあるフェルマー数の素因子を考えることにより、無数に素数を得る。実際、m に関する数学的帰納法により、簡単に F 0 F 1 ⋯ F m = F m + 1 − 2 {\displaystyle F_{0}F_{1}\cdots F_{m}=F_{m+1}-2} が得られるので、ある素数 p が2つのフェルマー数を割り切るとすると、p は 2 も割り切ることになって不合理である。 オイラーによる証明は、リーマンゼータ関数のオイラー積表示を用いたものである。 素数は有限個の p1, …, pn からなると仮定する。各素数 pi に対し、等比級数の公式により 1 1 − p i − 1 = ∑ k = 0 ∞ 1 p i k {\displaystyle {\frac {1}{1-{p_{i}}^{-1}}}=\sum _{k=0}^{\infty }{\frac {1}{{p_{i}}^{k}}}} が成り立つ。i = 1, …, n における両辺の総乗を取ると、任意の自然数は素数の積として一意に表せる（算術の基本定理）ことより、 ∏ i = 1 n 1 1 − p i − 1 = ∏ i = 1 n ∑ k = 0 ∞ 1 p i k = ∑ m = 1 ∞ 1 m {\displaystyle \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年に発表した、より簡潔な証明である。 素数の逆数和は収束すると仮定する。n 番目の素数を pn で表すことにすると、ある番号 k が存在して ∑ i = k + 1 ∞ 1 p i < 1 2 {\displaystyle \sum _{i=k+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {1}{2}}} である。素数全体を2つのグループに分け、p1, …, pk を「小さい」素数、pk+1 以降を「大きい」素数と呼ぶことにする。N 以下の自然数で、「大きい」素数で割れる数と、「小さい」素数でしか割れない数に分け、前者の個数を N1、後者の個数を N2 とおく。当然 N = N1 + N2 である。 以下、N1 と N2 の大きさを見積もる。N 以下の p の倍数の個数は、床関数を用いて ⌊ N p ⌋ {\displaystyle \left\lfloor {\frac {N}{p}}\right\rfloor } と表せるから、 N 1 ≤ ∑ i = k + 1 ∞ ⌊ N p i ⌋ ≤ ∑ i = k + 1 ∞ N p i < N 2 {\displaystyle 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 = uv2（u は平方因子を含まない） と表す。u の可能性は高々 2k 通りであり、v2 ≤ x ≤ N であるから、 N 2 ≤ 2 k N {\displaystyle N_{2}\leq 2^{k}{\sqrt {N}}} を得る。よって、 N = N 1 + N 2 < N 2 + 2 k N {\displaystyle N=N_{1}+N_{2}<{\frac {N}{2}}+2^{k}{\sqrt {N}}} となる。しかし、この式は N = 22k+2 に対して成り立たない。 フュルステンベルグの証明は、トポロジーを用いたものである。彼は、まだ学部生であった1955年に、証明を発表した。 整数全体からなる集合 Z に、両方向への無限等差数列 a Z + b = { a x + b ∣ x ∈ Z } {\displaystyle a\mathbb {Z} +b=\{ax+b\mid x\in \mathbb {Z} \}} （ただし、a, b は整数で、a ≠ 0）全体を開基とする位相を定める。換言すれば、この位相における開集合は、（空集合であるか）任意個の無限等差数列の和集合である。このとき、空でない有限集合は開集合ではないことに注意する。 任意の無限等差数列は、開集合であると同時に、 a Z + b = Z ∖ ( ⋃ i = 1 a − 1 ( a Z + b + i ) ) {\displaystyle a\mathbb {Z} +b=\mathbb {Z} \setminus \left(\bigcup _{i=1}^{a-1}(a\mathbb {Z} +b+i)\right)} という表示により、閉集合でもある。p1, …, pn が素数全体と仮定すると、 A := ⋃ i = 1 n p i Z {\displaystyle A:=\bigcup _{i=1}^{n}p_{i}\mathbb {Z} } は有限個の閉集合の和集合であるから閉集合である。したがって閉集合 A の補集合 Ac = Z∖A は開集合である。ところが ±1 以外の任意の整数は何らかの素数で割り切れるから、Ac = {±1} である。これは空でない有限集合であるため開集合ではなく、矛盾が生じる。 ライプニッツの公式をオイラー積の形で表すと π 4 = 3 4 × 5 4 × 7 8 × 11 12 × 13 12 × 17 16 × 19 20 × 23 24 × 29 28 × 31 32 × ⋯ {\displaystyle {\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年に発表されたフィリップ・サイダックによる証明は非常に簡潔である。 n は2以上の整数とする。n と n + 1 は互いに素 なので、N2 := n(n + 1) は少なくとも2つの異なる素因子を持つ。同様に、N2 と N2 + 1 は互いに素なので、N3 := N2(N2 + 1) は少なくとも3つの異なる素因子を持つ。この操作を続けることにより、任意に多くの異なる素因子を持つ数を構成することができるので、素数は無数に存在する。