FANDOM


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

詳細

整数の集合に属する数a, bがあり、かつaは0ではないとする($ a, b \in \mathbb{Z} $, $ a \neq 0 $)。このとき、$ 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 $であり、お互いに素である。これは矛盾である。

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

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


1の約数は素数ではない

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

出典

  1. Prime number - MathWorld

関連項目

特に記載のない限り、コミュニティのコンテンツはCC-BY-SA ライセンスの下で利用可能です。