数学 Wiki
Advertisement

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

詳細

整数の集合に属する数a, bがあり、かつaは0ではないとする(, )。このとき、という式において、nが整数の集合に属する場合()、 このときの a を b の約数 と言う。

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

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

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

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

性質

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

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

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

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

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

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

素数は無限にある

もし、素数が有限個である場合、と表現ができる。この集合を、仮にPとする。ここで、という数を仮定する。

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

このとき、となるiが存在するとする。このとき、 と表記でき、とおく。このとき、と置くことができる。しかし、の補題によって、であり、お互いに素である。これは矛盾である。

この帰結から、もしqの約数であるrを求める場合、P以外の素数を仮定しなければならない。しかし、我々はPの集合を有限個であると仮定した。よって、Pの集合を有限で仮定したのがそもそも間違いである。従って、素数は無限個存在することが証明される。

素数は無限にあること自体は、紀元前300年頃、ユークリッドが証明した。


1の約数は素数ではない

約数を参照せよ。系により、1の約数は、1か、-1である。そして、素数において1の約数は存在しない。これは矛盾である。従って、1の約数は素数ではない。

出典

関連項目

Advertisement