素数

素数 (Prime number) とは、1より大きい整数で、1と自分自身以外で割り切れない数のことである^[1]。たとえば、2,3,5,7,11,13 である。

詳細[]

整数の集合に属する数a, bがあり、かつaは0ではないとする( $a, b \in \Z$ , $a\ne0$ )。このとき、 $b = an$ という式において、nが整数の集合に属する場合( $n\in\mathbb{Z}$ )、このときの a を b の約数と言う。

正の整数のみを考えている時には、単に「約数」というとき、「正の約数」を意味することがある。ここで、正の約数とは、約数であり、かつ正の整数である数を言う。

例えば、bを15と置く場合、正の約数は1, 3, 5, 15 となる。これらはそれぞれ

$15=1n$

$15=3n$

$15=5n$

$15=15n$

とできる。この場合、nは整数の集合に属しているのは疑いない(1nならn = 15, 3n なら n = 5 ...) 。しかし、同様にnが整数であるときに、bが下の数しかとらない整数を考えることも可能である。

$a=1n$

$a=an$

つまり、正の約数として1か、あるいはそれ自体以外の整数を取らない整数(2, 3, 5, 7……など)の場合、これを素数と呼ぶ。また、定義として、1は素数として含まれない。

性質[]

1より上の整数nは、nの約数でかつ素数であるものが存在する[]

nが素数であった場合、それ自身の約数が素数である。従って、nが素数である場合は問題が無い。

次に、nが素数ではないと仮定する。言い換えれば、nが合成数だと仮定する。このとき、

$1<m<n$ を mの約数とする。1とnは素数ではない、と仮定されているので、範囲に含まなくてよい。

ここで最小の合成数を考える。最小の合成数は4である。このとき、 $1<m<4$ の範囲を取る。4の約数は2であり、この中におさまる。整数は常に合成数か素数である。

従って、1より上の整数は、nの約数でかつ素数であるものが存在することが証明される。

素数は無限にある[]

もし、素数が有限個である場合、 $p_{1},p_{2},p_{3},..p_{N}$ と表現ができる。この集合を、仮にPとする。ここで、 $q=p_{1}..p_{N}+1$ という数を仮定する。

素数ではないということは、その数は合成数である。そのとき、1かそれ自身以外の約数を取れなければならない。「1より上の整数は、nの約数で素数であるものがある」という命題、かつ合成数の定義により、1とそれ自身以外の約数を持たなければならない。この場合ならば、qの約数rにおいて $r\in P$ である必要がある。

このとき、 $r=p_{i}$ となるiが存在するとする。このとき、 $p_{i}..p_{1}{\dot {p}}_{N}$ と表記でき、 $s=p_{1}..p_{N}$ とおく。このとき、 $q=s+1$ と置くことができる。しかし、素の補題によって、 $s\nmid s+1$ であり、お互いに素である。これは矛盾である。