素数が無数に存在することの証明
しかし、これは p1, ..., pn が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無限に存在する。
この形の証明のために、「ユークリッドは、背理法で素数が無数にあることを証明した」「ユークリッドの証明は、存在のみを示しており、具体的な構成の手続きを示していない」「ユークリッドは、最初のいくつかの素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、いずれも正しくない。『原論』の証明は背理法ではなく、直接証明(英語版)である場合分け(英語版)によるものである。また、最後の主張は「 2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 = 30,031 」という反例により、歴史的にのみならず数学的にも誤りである。
1878年、クンマーは、P + 1 の代わりに P − 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 の倍数である。もし素数が有限個ならば π は有理数として表すことができる。しかし π は無理数なので、背理法より素数は無限に存在する。
ゴールドバッハは、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 も割り切ることになって不合理である。