素数の間隔に最大値がないことの３通りの証明

連続する $n-1$ 個の数を以下のように構成する：

$n!+2,\:n!+3,\cdots ,n!+n$

ここで，$2\leq k\leq n$ に対して $n!+k$ は $k$ の倍数なので，上記の数はいずれも合成数である。したがって，これは長さ $n-1$ 以上の素数砂漠（の一部）である。

これは任意の $n$ について成立するので，いくらでも長い素数砂漠が構成できる。

素数は無限に存在するので，その中から $N$ 個，$p_1,\:p_2,\cdots,\:p_N$ を取ってくる。

次に，以下の $N$ 本の連立合同式を考える：

$x\equiv k\pmod{p_k}\:(k=1,\:2,\cdots, N)$

中国剰余定理によりこの連立合同式には解が存在するので，その解（のうち十分大きいもの）を $n$ とおく。

すると，$1\leq k\leq N$ に対して $n-k$ が $p_k$ の（二倍以上の）倍数であるので $n-N$ から $n-1$ までが全て合成数，つまり長さ $N$ の素数砂漠になっている。

背理法で証明する。もしいくらでも長い素数砂漠がない，つまり素数砂漠の長さの最大値 $M$ が存在すると仮定する。

このとき，$M+1$ 個のうち少なくとも1個は素数なので，

$\pi (n)\geq \dfrac{n}{M+1}-1$

よって，

$\displaystyle\lim_{n\to\infty}\dfrac{\pi(n)}{n}\\ \geq\displaystyle\lim_{n\to\infty}\left(\dfrac{1}{M+1}-\dfrac{1}{n}\right)\\ =\dfrac{1}{M+1}$

これは（※）に矛盾。