素数が無限にあることの4通りの証明

素数が無限に存在することのいろいろな証明を紹介します。

素数は無限にある

1より大きい整数で,約数が1とその数自身のみであるものを素数と言います。2,3,5,7,112,3,5,7,11 などが素数です。

素数一覧(4桁以下,番号つき)で紹介したように素数はたくさんありますが,実は,素数は無限にある(つまり,任意の整数 NN に対して,素数は NN 個以上ある)ことが知られています。

この記事では,素数が無限にあることの証明を4通り紹介します。

1.背理法による有名な証明

ユークリッドによる証明です。紀元前に発見されたものです。

方針

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

証明

素数が有限個しかないと仮定する。その有限個の素数全体を p1,p2,,pnp_1,p_2,\cdots,p_n とおく。

ここで,p=p1p2pn+1p=p_1p_2\cdots p_n+1 という数を考えると,pp はどの pip_i でも割り切れない(つまり,どの素数でも割り切れない)ので素数となる(※)。しかし,pp はどの pip_i よりも大きく,素数全体の集合に入っていないので矛盾。よって,背理法により素数は無限に存在する。

※の補足:上記の証明では,

p1,p2,,pnp_1,p_2,\cdots,p_n が素数ならば p=p1p2pn+1p=p_1p_2\cdots p_n+1 も素数である

という主張をしているわけではありません。実際, この主張は正しくありません(例えば,2277 は素数ですが 2×7+1=152\times7+1=15 は素数ではありません)。「素数が有限個しかない」という(偽である)仮定のもとで導かれる主張です。

2.サイダックによる美しい証明

方針

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

証明

N1N_1 を2以上の整数とする。 N1N_1N1+1N_1+1 は互いに素なので N2=N1(N1+1)N_2=N_1(N_1+1) は異なる素因数を2個以上持つ。

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

試しに N1=2N_1=2 としてやってみると, N2=6=2×3N_2=6=2\times 3 となり新しい素数 33 を得ます。N3=42=2×3×7N_3=42=2\times 3\times 7 となり,新しい素数 77 を得ます。N4=1806=2×3×7×43N_4=1806=2\times 3\times 7\times 43 となり新しい素数 4343 を得ます。

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

  1. フェルマー数を用いた証明

22n+12^{2^n}+1 という形の数をフェルマー数と言います。

  • フェルマー数どうしは互いに素
  • 当然ながら,全てのフェルマー数が素因数を最低1つは含んでいる

という事実から,素数が無限にあることが証明されます。

フェルマー数どうしが互いに素であることの証明はフェルマー数とその性質に記載しています。

4.オイラーによる証明

方針

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

証明

素数が有限個しかないと仮定する。その有限個の素数全体を p1,p2,,pnp_1,p_2,\cdots,p_n とおく。

素因数分解の一意性より,i=1nk=01pik=k=11k()\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…が発散することの証明

一方,この等式の左辺は無限等比級数の公式から計算できる:

i=1nk=01pik=i=1npipi1\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+12+122+)(1+\dfrac{1}{2}+\dfrac{1}{2^2}+\cdots) ×(1+13+132+)\times(1+\dfrac{1}{3}+\dfrac{1}{3^2}+\cdots) ×(1+15+152)\times(1+\dfrac{1}{5}+\dfrac{1}{5^2}\cdots)\cdots

余談

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

ディリクレの算術級数定理

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

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

Tag:無限和,無限積の美しい公式まとめ

Tag:素数にまつわる覚えておくべき性質まとめ