素数が無限に存在することの証明
この記事は，この記事の著者であるナンブキトラのはてなブログ記事(参考文献XND)をMathlog用に書き直したものである．
この記事では素数の無限性を証明する．
本文
まず最初に合成数や素数の定義を確認しておく．
$n, m\in \zz_{\ge 1}$とする．$n=km$となる$k\in \zz_{\ge 1}$が存在するときに$m$は$n$の約数という．$p\in \zz_{\ge 1}$が素数であるとは$p\neq 1$であり尚且つ$p$が$1$と自分自身以外の正の約数を持たないときにいう．$n$の素因数とは素数であり$n$を割り切れる数のことである．そして$n\in \zz_{\ge 1}$に対して$1< a, b< n$を満たす$a, b\in \zz_{\ge 1}$が存在して$n=ab$を満たすならば$n$を合成数と呼ぶ．
合成数の定義から次がわかる．証明は省略する．
$n$が合成数であることと$n\neq 1$で尚且つ$n$が素数でないことは同値である．
次に$1$より大きい整数が必ず素因数を持つことを自然数の整列性から導こう．
$n\in \zz_{\ge 1}$が$n\neq 1$を満たすならば$n$は素因数を持つ．
まず集合$A$を
$$
A =\{\, n\in \mathbb{N}
\mid
\text{
$n\neq1$かつnは素因数を持たない}
\, \}
$$
と定義する．証明したい命題は$A= \emptyset$と同値である.背理法によって証明する．今$A\neq \emptyset$と仮定すると$A$の最小元が存在する．そこで$a=\min A$と置く．今$a\in A$なので$a\neq 1$であり，なおかつ$a$は素数ではない．よって
命題１
より$a$は合成数である．ゆえに $1< x,y< a$ を満たす$x, y\in \zz$を用いて$a=xy$と書ける．数$a$の$A$における最小性から$x,y\not\in A$でなければならない．よって$x,y$は素因数を持つ．すると$a=xy$なので$a$も素因数を持つことになり，$a\in A$に矛盾する．$\Box$
最後にこの記事の主定理を証明する．
素数は無限に存在する．
任意の$n>1$に対してそれよりも大きい素数が存在することを言えば良い．
$n!$を$1$から$n$までの間の自然数の積とする．つまり階乗のことである．このとき$n!+1$は
命題２
より素因数を持つ．その素因数の一つを$p$とする．$(n!+1)-n!=1$なので，もしも$p$が$n!$の約数だとすると$p$は$1$を割り切ることになり$p=1$となる．これは$p$が素数であることに矛盾する．よって$p$は$n!$の約数ではない．すると$n!$の定義から$n< p$がわかり，$n$より大きい素数の存在がわかった．$\Box$
注釈
ここで与えた証明は練習用にはちょうど良い原稿量であるが，新規性のあるものではないだろう．実際，この記事の証明はSaidakSaidakによる証明とほぼ同じであると思われる．この記事での証明のポイントは$n$と$n+1$が互いに素であることとユークリッドの証明よろしく階乗を用いるところである．
