素数
素数
Def. （素数と合成数）
自然数nが1とそれ自身以外に約数を持たないとき素数という。
それ以外のすべての自然数を合成数とよぶ
Lem.
もしnが合成数ならば、素数pが存在して、$ p|n
proof.
$ S:=\set{合成数で素数の約数を持たない}\sub\N
$ 示す式:S=\varnothing
$ S\neq \varnothingと仮定すると
$ \Nの整列性より、$ Sには最小元$ mが存在する。
自然数の整列原理
$ mは合成数より、
$ m=m_1m_2,1<m_1<m,1<m_2<m
$ m_1\notin Sつまり、
$ m_1は素数であるか、素数を約数に持つ。
したがって、ある素数pが存在して
$ p|m_1
$ p|m_1m_2=m
$ m\in Sに矛盾。
Thm.
素数は無限にある
proof.
もしそうでないとする。
$ p_1,\dots,p_n:素数の有限リスト
次のような数$ Bを考える。
$ B:=p_1p_2\dots p_{k}+1
$ \forall i ,p_i<Bより$ Bは素数ではない。
Lem.より、$ \exists j,p_j|B
一方で、
約数#6a4badd800000000004ce6c0より、
4. $ a|bかつ$ a|cならば$ a|bx+cy、$ \forall x,y\in\mathbb{Z}
$ p_j|p_1,\dots,p_n
$ p_j|B-p_1,\dots,p_n=1
これは矛盾
1を割り切る素数は存在しないから
1の約数は±1だけである。1は素数ではない。ゆえにこうなる。