2014/04/23

素数が無限にあることの美しい証明

分野: 整数問題  レベル: マニアック

素数は無限に存在する


この有名な性質の3通り証明を紹介します。素数が無限にあることの証明方法はいろいろ発見されていますが,その中でも簡潔で美しい証明方法を集めました。

1:ユークリッドによる証明(一番有名)
2:オイラーによる証明(オススメ)
3:サイダックによる証明(最近発見された)

1:ユークリッドによる証明

方針:背理法で証明します。素数たちからより大きい素数を構成することで矛盾を導きます。

証明

素数が有限個しかないと仮定する。その有限個の素数全体を $p_1,p_2,\cdots,p_n$ とおく。
ここで,$p=p_1p_2\cdots p_n+1$ という数を考えると,$p$ はどの $p_i$ でも割り切れないので素数となる。しかし,$p$ はどの $p_i$ よりも大きく,素数全体の集合に入っていないので矛盾

2:オイラーによる証明

方針:同様に背理法で証明します。任意の自然数が素数の積として一意に表せるという事実を用います(素因数分解の一意性)。「有限=無限」という等式を作って矛盾を示します。

証明

素数が有限個しかないと仮定する。その有限個の素数全体を $p_1,p_2,\cdots,p_n$ とおく。
素因数分解の一意性より,$\displaystyle\prod_{i=1}^n\sum_{k=0}^{\infty}\dfrac{1}{p_i^k}=\sum_{k=1}^{\infty}\dfrac{1}{k}\cdots(※)$
この等式の右辺は無限大となる。→調和級数1+1/2+1/3…が発散することの証明
一方,この等式の左辺は無限等比級数の公式から計算できる:
$\displaystyle\prod_{i=1}^n\sum_{k=0}^{\infty}\dfrac{1}{p_i^k}=\prod_{i=1}^n\dfrac{p_i}{p_i-1}$
これは有限値なので,有限=無限となり矛盾。

$※$はオイラー積表示と呼ばれる,非常に美しい等式です。「全ての素数の組み合わせの積」と「全ての自然数」が一対一対応していることを表しています。オイラー積表示の左辺を具体的に書き下してみるとイメージが分かりやすいでしょう。
$(1+\dfrac{1}{2}+\dfrac{1}{2^2}+\cdots)$ $(1+\dfrac{1}{3}+\dfrac{1}{3^2}+\cdots)$ $(1+\dfrac{1}{5}+\dfrac{1}{5^2}\cdots)\cdots$

3:サイダックによる証明

次々と新しい素因数を作り出していく操作が無限回繰り返せることを示します。 $n$ と $n+1$ は互いに素という重要な性質を用います。

証明

$N_1$ を2以上の整数とする。 $N_1$ と $N_1+1$ は互いに素なので $N_2=N_1(N_1+1)$ は異なる素因数を2個以上持つ。
更に,同様な理由から $N_3=N_2(N_2+1)$ は異なる素因数を3個以上持つ。これを繰り返すといくらでも多くの異なる素因数を持つ数が生成できるので素数は無限に存在する。

ユークリッドの証明方法に勝るとも劣らない簡潔な証明です。この方法が21世紀になってから発見されたというのも驚きです。


余談1:フェルマー数を用いた証明もなかなかエレガントです。→フェルマー数とその性質

余談2:「素数が無限に存在する」よりも強い主張である「ディリクレの算術級数定理」というものがあります:

$a$ と $b$ が互いに素な自然数のとき $an+b$ ($n$ は自然数)の形で表せる素数は無限に存在する。

ディリクレの算術級数定理の証明はかなり難しいようです

Tag: 無限和,無限積の美しい公式まとめ
Tag: 素数にまつわる覚えておくべき性質まとめ

分野: 整数問題  レベル: マニアック