素数

概要

この世の中で1番美しいと言われる、数字の羅列のこと(偏見)。 自然数の中に存在しており、2や3や5のように、1と自分自身以外に約数を持たない数の事。また、未だにその規則性は発見されていない。

念の為言っておくが、1は素数じゃないぞ。確かに、「1と自分自身以外の数で割れない」という素数の定義には当てはまる。しかし1を素数と定義してしまうと全ての整数は1と-1の倍数であり、つまり1は全ての自然数の約数となってしまう。そうすると素数は1以外になくなってしまうこれでは素数自体の定義すら矛盾してしまう。このことから数学上の定義に矛盾しないよう1は素数では無い。結局、数学的に都合が悪いからってだけ。

先に「素数の規則性は見つかっていない」と書いたが、素数が無限に続くことは知られている。その証明はユークリッドの『原論』にも載っている。

素数が無限にあることの証明

まず、素数が有限であると仮定する。もしそうならば、全ての素数に1から番号を振ると、番号はある自然数nで終わるはずである。これらは P1,P2,P3.....Pn の数列として表せる（素数のprime numberからpとした）。 ここで、有限個の素数を全てかけあわせ、1を足した数をNとして考える。すると、 N=P1・P2・P3.....Pn+1 と表すことができる。 この時Nは素数かを考えると、仮定の素数P1,P2,P3.....Pnのいずれでもないため素数では無い。では、NはP1,P2,P3.....Pnのいずれかの素数で割れるはずだが、+1が式の最後にあるためどの素数で割っても必ず1余る。つまり、ある数Nは素数でもなく素数でも割れない。こうした矛盾が発生するのは仮定が正しくないためである。よって、背理法により素数は無限にあることが分かる。 ちなみにこの証明方法は原論に表記されている方法で、他にもいくつか証明方法はある。

アリストテレス（エラトステネス）の篩

古代ギリシャの哲学者アリストテレスが発見した、初歩的な素数の一覧表のこと。 具体的な方法は、 ①自然数の表を作る ②2の倍数、3の倍数、5の倍数、、、というように 次々と素数の倍数を消す と単純かつ初歩的である。しかし現在コンピュータを使い素数を抜き出す場合はこの方法が使われているなど、popbobがリーマン予想を発見するまでは最も効率的な方法とされている。

メルセンヌ素数

フランスのカトリック教会の修道士マルン・メルセンヌ（1588～1648）の、素数に関する予想。

Nが257以下の時、N=2n-1の式で計算される数が素数になるのはNが2.3.5.7.13.17.19.31.67.127.257の場合である

というもの。 ただし、現在はリュカ・テストという素数判定式により2の61²-1の数でメルセンヌの予想は外れることがわかっている。

オイラーの二次式

スイスの数学者レオンハルト・オイラー（1707～1783）も二次式を用いた素数製造式をいくつも考案した。そのひとつが

N=n2-n+41

の形で表されるものである。 現在はこの二次式も万能ではないことが分かっているが、n=1～40のとき、この式は成立する。

ウィルソンの定理

ウィルソンの定理とは、

ある整pが、素数かどうかを確かめたいとする。もし、1から（p-1までの数を全て掛け算してるpで割り算した時に、あまりが（p-1）ならば、pは素数である。

というものである。例えば 13という整数は 1・2・3・4・5・6・7・8・9・10・11・12= 479001600=13・36846276,,,12より素数だとわかる。ただ問題は、確かめたい数の大きいと桁があまりにも計算が膨大になってしまうため、絶望的な実用性だということである。 WikiWiki