素数が無限に存在すること証明を $3$ 通り紹介します．
・背理法 ・数学的帰納法 ・ $n$ と $n+1$ は互いに素 ・ $1$ 以上の整数は必ずひとつ以上の素因数をもつ
素数とは，$1$ より大きく，$1$ と自分自身以外に約数をもたない自然数のことです．小さい順に， $$2,3,5,7,11,13,17,19,23…$$ とつづいていきます．実は，素数が無限に多く存在することが紀元前 $3$ 世紀ごろのユークリッドの著書「原論」ですでに証明されています．
以下の証明は，ユークリッドが実際に書いた証明とは若干異なりますが，似たような方法です．
証明： 背理法で示す．素数が有限個しかないと仮定する．$p_1 < p_2 < \cdots < p_n$ をすべての素数とする． $$N=p_1p_2\cdots p_n +1$$ とおくと，$N$ は $p_1,…,p_n$ のいずれでも割り切れない (つまりすべての素数で割り切れない) ので，素数である．しかし，$N$ は $p_1,…,p_n$ のいずれでもないので，矛盾である．したがって，素数は無限に存在する．
ひとつ注意すべきことは，上の証明を見て，『有限個の素数 $p_1,…,p_n$ が与えられたら，$p_1p_2\cdots p_n+1$ は素数』と思ってはいけません．この命題は偽です．実際，$3\cdot 5+1=16$ という簡単な反例が存在します．
上の証明では，素数が有限個しかないという (実際には偽であるような) 仮定のもとで議論を行っているので，そのようなことが起こるのです．
背理法を使わず，直接証明することもできます． ゴールドバッハはフェルマー数の性質を使って証明しました．
フェルマー数とは，$2^{2^n}+1$ の形で表される自然数のことです．
つまり， $$F_n=2^{2^n}+1 (n=0,1,2,…)$$ とおいたとき，$F_n$ を $n$ 番目のフェルマー数と呼びます．フェルマー数は小さい順に， $$3,5,17,257,65537,…$$ とつづいていきます． つぎのふたつの事実が成り立つことはすぐにわかります． ・フェルマー数は無限に存在する ・すべてのフェルマー数は奇数である さらに，フェルマー数は以下の漸化式が成り立ちます．
フェルマー数の漸化式: $F_n=2^{2^n}+1$ をフェルマー数とする．このとき，次の漸化式が成り立つ． $$\large F_n=F_0F_1\cdots F_{n-1}+2 (n \ge 1)$$
証明： 数学的帰納法で示す． $n=1$ のときは，$F_1=F_0+2$ なので成り立つ．
$$ F_n=F_0F_1\cdots F_{n-1}+2$$ が成り立つと仮定すると， $$F_{n+1}=2^{2^{n+1}}+1=(2^{2^n}+1)(2^{2^n}-1)+2=F_n(F_n-2)+2$$ $$=F_n(F_0F_1\cdots F_{n-1})+2 (\leftarrow \text{帰納法の仮定より})$$ $$=F_0F_1\cdots F_{n-1}F_n+2$$ となる．したがって， $$F_n=F_0F_1\cdots F_{n-1}+2 (n \ge 1)$$ が成り立つ．
この漸化式から，フェルマー数に関するつぎの重要な性質が導かれます．
フェルマー数の性質: 相異なるフェルマー数は互いに素である．
証明： $F_n=2^{2^n}+1$ をフェルマー数とする．
相異なるフェルマー数 $F_n,F_m (n < m)$ を任意に選ぶ．$m$ について，さきほど示した漸化式を考える. $$F_m=F_0F_1\cdots F_{m-1}+2$$ $d$ を $F_n,F_m$ の公約数とすると，$d$ は $F_m,F_0F_1\cdots F_{m-1}$ をともに割り切るので，上の式から，$d$ は $2$ を割り切る．したがって，$d=1,2$ であるが，すべてのフェルマー数は奇数なので，$d=1$．よって，$F_n,F_m$ は互いに素．
では，フェルマー数をつかって，素数が無限にあることを証明してみましょう．
素数が無限に存在することの証明： 各フェルマー数 $F_n$ $（n \ge 0）$ に対して，その素因数 $p_n$ をそれぞれひとつ選ぶ．すると，相異なるフェルマー数は互いに素なので，$p_0,p_1,…$ は相異なる素数でなければならない．したがって，フェルマー数は無限に存在するので，素数も無限に存在する．
2006年，Filip Saidak は非常に簡潔な証明を提出しました．
素数が無限に存在することの証明 (Saidak)： 自然数 $n >1 $ をひとつ選ぶ．$n,n+1$ はともにひとつ以上の素因数をもっており，$n,n+1$ は互いに素なので， $$N_2=n(n+1)$$ とおくと，$N_2$ は $2$ つ以上の素因数をもっている．さらに，$N_2,N_2+1$ は互いに素なので， $$N_3=N_2(N_2+1)$$ とおくと，$N_3$ は $3$ つ以上の素因数をもっている．この操作は無限に繰り返すことができる．したがって，いくらでも多くの素因数をもつ数が構成できるので，素数は無限に存在する．
