📂整数論

ユークリッドの証明:素数は無限に存在する

定理¹

素数は無限に多く存在する。

説明

素数が無限であることを証明する方法はいくつもある。その中でも最も簡単なユークリッドの方法を紹介する。この証明は単純であるだけでなく、非常に美しいことでも有名だ。

証明

素数が$n$個だけ存在すると仮定しよう。$n$個の素数をそれぞれ$p_1, p_2, \cdots , p_n$とし、$p_{n+1}=p_1 p_2 \cdots p_n + 1$について考えてみよう。

• もし$p_{n+1}$が素数ならば、$p_{n+1}$は他のどの素数とも等しくない新しい素数となる。これは仮定に矛盾する。
• もし$p_{n+1}$が素数でないならば、$p_{n+1}$は素数$q_1, q_2, \cdots , q_m$の積として表される。しかし$q_1$もまた素数であるため、$p_1, p_2, \cdots , p_n$のいずれとも等しくない。これは$q_1$が$n$個の素数のうちの一つではない新しい素数であることを意味する。これは仮定に矛盾する。

したがって、素数は無限に多く存在する。

■

関連リンク

• オイラーの証明