素数とは，1と自分自身以外に約数を持たない正の整数である。例としては，$2,3,5,7,11,13,17,19,23,\cdots$が挙げられる。これまで，素数にまつわる様々な定理が証明されてきたが，素数の規則性についてはまだ解明されていない。ミレニアム懸賞問題の1つである「Riemann予想」が解かれれば，素数の規則性が解明されるのではないかと言われているが，未解決である。
「素数は有限個しか存在しないのか？」という素朴な疑問が生まれる。結論は素数は無限個存在する。この事実は紀元前から知られており，様々な数学者によって証明がなされた。
素数が有限個($n$個)存在すると仮定する。その素数全体を$p_{1}, p_{2}, \ldots , p_{n}$と表すことにする。ここで，
$$
p := p_{1} p_{2} \cdots p_{n} + 1
$$
という数を考えると，$p$はいずれの$p_{i}\ (1 \leq i \leq n)$でも割り切れない。よって，$p$は$n+1$個目の素数となるが，これは素数が$n$個であることに反する。よって，素数は無限個存在する。
素数が有限個($n$個)存在すると仮定する。その素数全体を$p_{1}, p_{2}, \ldots , p_{n}$と表すことにする。素因数分解の一意性により，
$$
\prod_{i=1}^{n} \sum_{k=1}^{\infty} \dfrac{1}{p_{i}^{k}} = \sum_{k=1}^{\infty} \dfrac{1}{k}
$$
この式の右辺は調和級数であり，無限大に発散する。左辺については等比無限級数の公式から
$$
\prod_{i=1}^{n} \sum_{k=1}^{\infty} \dfrac{1}{p_{i}^{k}} = \prod_{i=1}^{n} \dfrac{p_{i}}{p_{i}-1}
$$
であり，これは有限確定値である。これは右辺が発散することに反する。よって，素数は無限個存在する。
Fermat数とは，
$$
F_{n} := 2^{2^{n}} +1
$$
を満たす数である。例えば，$3,5,17,257,\cdots$はFermat数である。この数から素数の無限性が証明できるというのだから驚きである。
まず，Fermat数の漸化式を与えよう。$2^{2^{n}}+1 = \left( 2^{2^{n-1}} \right)^2 + 1$であることに注意すると，
$$
F_{n} - 2 = 2^{2^{n}} - 1 = (2^{2^{n-1}} + 1)(2^{2^{n-1}} - 1) = F_{n-1}(F_{n-1}-2)
$$
よって，次の漸化式
$$
F_{n} - 2 = F_{n-1}(F_{n-1}-2)
$$
が得られる。この漸化式を順次適用すると
$$
F_{n} - 2 = F_{n-1}(F_{n-1}-2) = F_{n-1}F_{n-2}(F_{n-2}-2) = \cdots = F_{n-1}F_{n-2} \cdots F_{2} F_{1} F_{0} (F_{0} -2)
$$
となる。$F_{0} = 2 + 1 = 3$なので，次の命題が得られる。
$$ F_{n} = \begin{eqnarray} \left\{ \begin{array}{ll} F_{n-1}F_{n-2} \cdots F_{2} F_{1} F_{0} F_{0} + 2 & (n \geq 1)\\ 3 & (n = 0) \end{array} \right. \end{eqnarray} $$
命題1を使えば，次の命題が証明できる。
相異なる0以上の整数$m, n$に対して，$F_{m}$と$F_{n}$は互いに素である。
$m$と$n$は入れ替えても一般性を失わないので，$m < n$とする。命題1より
$$
F_{n} = F_{n-1}F_{n-2} \cdots F_{m} \cdots F_{1} F_{0} + 2
$$
が成り立つ。ここで，$F_{m}$と$F_{n}$を共に割り切る素数が存在するとし，それを$p$とする。このとき，上の式の右辺第1項は$p$で割り切れる。$F_{n}$も$p$で割り切れるが，右辺第2項の$2$も割り切らなければならないので，$p=2$であることがわかる。一方，$F_{m}$と$F_{n}$は定義よりどちらも奇数なので，素因数$2$を持たない。よって，$F_{m}$と$F_{n}$は互いに素である。
この命題2が証明できれば，素数の無限性が証明できる。
各Fermat数$F_{n}$($n \geq 0$)に対して，その素因数$p_{n}$をそれぞれ1つ選ぶ。命題2より，Fermat数は互いに素なので，これにより得られた素数$p_{1}, p_{2}, \ldots $はいずれも相異なる。Fermat数は無限に存在するので，このようにすれば無限に素数を生成できる。よって，素数は無限個存在する。