素数の無限性

この文章では素数の無限性を証明する．

定義 1.

$n,m\in {\mathbb{Z}}_{\ge 1}$ とする． $n=km$ となる $k\in {\mathbb{Z}}_{\ge 1}$ が存在するときに $m$ は $n$ の 約数 という． $p\in {\mathbb{Z}}_{\ge 1}$ が 素数 であるとは $p\ne 1$ であり尚且つ $p$ が $1$ と自分自身以外の正の約数を持たないときにいう． $n$の素因数 とは素数であり $n$ を割り切れる数のことである． そして $n\in {\mathbb{Z}}_{\ge 1}$ に対して を満たす $a,b\in {\mathbb{Z}}_{\ge 1}$ が存在して $n=ab$ を満たすならば $n$ を 合成数 と呼ぶ．

合成数の定義から次がわかる．

命題 2.

$n$ が合成数であることと $n\ne 1$ で尚且つ $n$ が素数でないことは同値である．

命題 3.

$n\in {\mathbb{Z}}_{\ge 1}$ が $n\ne 1$ を満たすならば $n$ は素因数を持つ．

証明.

まず $A=\{n\in \mathbb{N}\mid n\ne 1\text{ かつ }n\text{ は素因数を持たない}\}$ とおく． 命題は $A=\mathrm{\varnothing }$ と同値である. 今 $A\ne \mathrm{\varnothing }$ と仮定すると $A$ の最小元が存在する． $a=\min A$と置く． $a\in A$ なので $a\ne 1$ であり， $a$ は素数ではない． よって命題 2 より $a$ は合成数である． ゆえに と書ける． 数 $a$ の最小性から $x,y\notin A$ である． このことから $x,y$ は素因数を持つ． すると $a$ も素因数を持つことになり矛盾する． ∎

定理 4.

素数は無限に存在する．

証明.

任意の $n>1$ に対してそれよりも大きい素数が存在することを言えば良い． $n!$ を $1$ から $n$ までの間の自然数の積とする． このとき $n!+1$ は命題 3 より素因数を持つ． その素因数の一つを $p$ とする． $(n!+1)-n!=1$ なので， もしも $p$ が $n!$ の約数だとすると $p$ は $1$ を割り切ることになり $p=1$ となる． これは $p$が素数であることに矛盾する． よって $p$ は $n!$ の約数ではない． ゆえに $n!$ の定義から である. ∎