素数は無限個あります、ていうことの証明

ちょっと会社に行く電車の中で気になったので（笑）、復習がてら。

(証明)
背理法で証明する。仮に無限個でなく有限個だとする。*1
すると、一番大きな素数が存在するはずなので、それを $n$ とおく。
このとき、数 $N$ を次で定義する： $N:=n!+1$
以下の２通りについて考えてみる。

$N$ が素数のとき

　 $N>n$ なので $n$ が最大の素数であるであることに反する。

$N$ が素数でないとき

　 $N$ は次のような積に分解できる。 $N=m_1*m_2*...*m_p, m_1, m_2, ..., m_p>1$
　 $N=n!+1$ だから $1=m_1*m_2*...*m_p-n!$ .右辺は最大の素数までの全ての整数の積だから、例えば $m_1$ を含む。よって、1が1以上の積に分解できることとなり矛盾。

(1), (2)のいずれにおいても矛盾が成立するため、素数は有限個とはなり得ない■

*1:背理法の仮定