素因数が存在すること

はじめに

2以上の自然数が素数の因数（素因数という）を持つことは自明なのだろうか？

そんな疑問を持ったので、ここに証明を書くことにしました。

証明の準備

素数の定義を確認しましょう。

自然数$${n}$$が素数であるとは、$${n}$$の正の約数が$${1}$$と$${n}$$しかないときをいう。

ただし、$${1}$$は素数ではないとします。

証明

さて、$${n}$$を2以上の自然数として、$${n}$$が素因数を持つことを証明しましょう。

集合$${A}$$を$${n}$$の2以上の約数全体からなる集合とします。

$${A}$$は$${n}$$を要素として持つので、空集合ではありません。

したがって、$${A}$$は自然数全体の空でない部分集合なので最小値$${m}$$を持ちます。

このとき、$${m}$$は$${n}$$の素因数であることが、背理法によって証明できます。

もし、$${m}$$が素数でないと仮定すると、$${m=pq}$$かつ$${2\leq p \leq q < m}$$を満たす自然数$${p, q}$$が存在します。

このとき、$${p}$$は$${A}$$の要素ですが、これは$${m}$$の選び方に矛盾します。

以上のことから、$${n}$$の素因数が存在することが証明されました。