素数が無数に存在することの証明とは？わかりやすく解説

素数が無数に存在することの証明（そすうがむすうにそんざいすることのしょうめい）は、古くは紀元前3世紀頃のユークリッドの『原論』に記され、その後も多くの証明が与えられている。素数が無数に存在することは、しばしばユークリッドの定理（ユークリッドのていり、英: Euclid's theorem）と呼ばれる。

ユークリッド

『原論』第9巻命題20^[1]で、素数が無数に存在することが示されている。その証明は、次の通りである^[2]。なお「任意」は誤訳と思われる。

$a, b, \dots, k$ を任意に与えられた素数のリストとする。その最小公倍数 $P ≔ a \times b \times \dots \times k$ に $1$ を加えた数 $P + 1$ は、素数であるか、合成数のいずれかである。素数であれば、最初のリストに含まれない素数が得られたことになる。素数でなければ、何らかの素数 $p$ で割り切れるが、 $p$ はやはり最初のリストに含まれない。なぜならば、リスト中の素数は $P$ を割り切るので、 $P + 1$ を割り切ることは不可能だからである。任意の素数のリストから、リストに含まれない新たな素数が得られるので、素数は無数に存在する。

この証明は、しばしば次のような背理法の形で表現される。

素数の個数が有限と仮定し、

p 1, \dots p n

が素数の全てとする。その積

P = p 1 \times \dots \times p n

に

1

を加えた数

P + 1

は、

p 1, \dots, p n

のいずれでも割り切れないので、素数でなければならない。しかし、これは

p 1, \dots, p n

が素数の全てであるという仮定に反する。よって、仮定が誤りであり、素数は無限に存在する。

この形の証明のために、「ユークリッドは、背理法で素数が無数にあることを証明した」「ユークリッドの証明は、存在のみを示しており、具体的な構成の手続きを示していない」「ユークリッドは、最初のいくつかの素数の積に1を加えた数が素数であることを証明した」などの誤解をする者がいるが、いずれも正しくない^[3]。『原論』の証明は背理法ではなく、直接証明（英語版）である場合分け（英語版）によるものである。また、最後の主張は「 2 × 3 × 5 × 7 × 11 × 13 + 1 = 59 × 509 = 30,031 」という反例により、歴史的にのみならず数学的にも誤りである。

1878年、クンマーは、 $P + 1$ の代わりに $P - 1$ を考えても、同様に証明できることを注意した^[4]。

ゴールドバッハ

ゴールドバッハは、1730年7月にオイラーに宛てた手紙の中で、フェルマー数

F_{n}=2^{2^{n}}+1

[1]

[2]

[3]

[4]

素数が無数に存在することの証明とは？ わかりやすく解説