素数の無限性

素数は無限に存在する。つまり、どのような有限個の素数の集合を考えても、それに含まれない素数が必ず存在する。

素数が有限個しか存在しないと仮定し、それらを\(p_1, p_2, \ldots, p_n\)とする。

これらの素数の積に1を加えた数を考える。\(N = p_1 p_2 \cdots p_n + 1\)とする。

\[ N = p_1 p_2 \cdots p_n + 1 \]

Nは\(p_1, p_2, \ldots, p_n\)のいずれでも割り切れない。なぜなら、Nを\(p_i\)で割ると1余るためである。

したがって、Nは素数であるか、または\(p_1, p_2, \ldots, p_n\)以外の素因数を持つ。

いずれの場合も、\(p_1, p_2, \ldots, p_n\)以外の素数が存在することになる。

これは、素数が有限個しか存在しないという仮定に矛盾する。

したがって、素数は無限に存在する。(証明終)