2015/01/16

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

分野: 整数問題  レベル: 数学オリンピック

いくらでも長い素数砂漠が存在する。

素数の間隔について

素数の間隔が広い場所,すなわち合成数が連続する場所を素数砂漠と言うことにします。例えば,$114$ から $126$ までの整数は全て合成数であり,長さ $13$ の素数砂漠です。この記事ではいくらでも長い素数砂漠があること,つまり任意の正の整数 $N$ に対して長さ $N$ 以上の素数砂漠があることを証明します。

素数は無限にあるので,素数砂漠の長さは必ず有限です。→素数が無限にあることの美しい証明
したがって「無限の長さの素数砂漠が存在する」と言ってしまうと間違いなので注意して下さい。

証明1(構成的)

実際に素数砂漠を構成する方法です。最もシンプルで分かりやすいでしょう。

証明

連続する $n-1$ 個の数を以下のように構成する:
$n!+2,\:n!+3,\cdots ,n!+n$

ここで,$2\leq k\leq n$ に対して $n!+k$ は $k$ の倍数なので上記の数はいずれも合成数である。したがって,これは長さ $n-1$ 以上の素数砂漠(の一部)である。
これは任意の $n$ について成立するのでいくらでも長い素数砂漠が構成できる。

証明2(中国剰余定理)

中国剰余定理という大道具を使うことでも証明できます,エレガント!→中国剰余定理と法が互いに素でない場合への拡張

証明

素数は無限に存在するのでその中から $N$ 個,$p_1,\:p_2,\cdots,\:p_N$ を取ってくる。
次に,以下の $N$ 本の連立合同式を考える:
$x\equiv k\:\mathrm{mod}\:p_k\:(k=1,\:2,\cdots, N)$
中国剰余定理よりこの連立合同式には解が存在するのでその解(のうち十分大きいもの)を $n$ とおく。

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

なお,この考え方を少し改良することで,国際数学オリンピック 1989 第5問が解けます。

証明3(素数定理)

超大道具「素数定理」を使います。

$1$ 以上 $n$ 以下の素数の数を $\pi(n)$ とおくと,素数定理より,
$\displaystyle\lim_{n\to\infty}\dfrac{\pi (n)\log n}{n}=1$
が成立します。よって,$\displaystyle\lim_{n\to\infty}\dfrac{\pi (n)}{n}=0$ です(※)。

証明

背理法で証明する。もしいくらでも長い素数砂漠がない,つまり素数砂漠の長さの最大値 $M$ が存在すると仮定する。
このとき,($M+1$)個のうち少なくとも1個は素数なので,
$\pi (n)\geq \dfrac{n}{M+1}-1$

よって,$\displaystyle\lim_{n\to\infty}\dfrac{\pi(n)}{n}\geq\lim_{n\to\infty}(\dfrac{1}{M+1}-\dfrac{1}{n})=\dfrac{1}{M+1}$
これは(※)に矛盾。

比較的簡単な事実の証明に素数定理などという大道具を持ち出すのは推奨されませんが,面白いので紹介しました!

ちなみに,間隔が2であるような二つの素数を双子素数と言います。
分野: 整数問題  レベル: 数学オリンピック