📂整数論

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

定理 ¹

素数は無限に存在する。

説明

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

証明

素数が$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$個の素数のうちの一つではない新しい素数という意味だ。これは仮定に矛盾する。

よって、素数は無限に存在する。

■

参照

• オイラーの証明