素数(そすう、英: primeあるいはprime number)とは、2 以上の自然数で、正の約数が 1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。
日本では、英: prime number の日本語への訳語は「素数」とすることが1881年(明治14年)に決まった[1][2]。
一般には、素数は代数体の整数環の素元として定義される(そこでは反数などの同伴なものも素数に含まれる)。このため、有理整数環 Z {\displaystyle \mathbb {Z} } での素数は有理素数(ゆうりそすう、英: rational prime)と呼ばれることもある。
最小の素数は 2 である。素数は無数に存在する。したがって、素数からなる無限数列が得られる[3]。2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,…
素数が無数に存在することは、紀元前3世紀頃のエウクレイデス(以下ユークリッド)の著書『原論』で既に証明されていた。そこでの証明は、背理法により次のようになる:『素数全体は有限個と仮定して、全ての素数の総乗に1を足した数をNとする。Nはどの素数で割っても余りが1となる。一方、Nはどの素数よりも大きいので、Nは素数ではない。すなわち、Nはある素数で割り切れる。これは、Nを素数で割った余りが1であることに矛盾する。ゆえに、素数は無数にある。』
自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。
分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。現在知られている最大の素数は、2018年12月7日に発見された、それまでにわかっている中で51番目のメルセンヌ素数 282589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ[4]。 100 以下の素数一覧 素数とは、自明な正の因数(1 と自分自身)以外に因数を持たない自然数であり、1 でない数のことである。つまり、正の因数の個数が 2 である自然数である。 例えば、2 は、正の因数が 1, 2 のみなので素数である。 素数でない 2 以上の自然数を合成数と呼ぶ。 合成数であることの判定法として、たとえば下記の4条件がある: 逆に、この4条件を、全て満たさない数でも素数とは限らない。例えば、91 は、正の因数が 1, 7, 13, 91 なので素数ではない。 また、2, 3 以外の素数は、最も近い6の倍数との差が 1 か −1 である。 2 でない素数は奇数であり、奇素数と呼ぶ。 100以下の素数は25個存在し、小さい順に次の通りである[3]。2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97詳細は「素数の一覧」を参照 「2 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する(算術の基本定理)。素因数分解の可能性から、素数全体の成す集合は、2以上の自然数全体の成す集合とその乗法からなる半群の最小[注釈 1]の生成系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる[6]。 素数の定義である「1 と自分自身でしか割り切れない」という条件(既約性)は、抽象代数学において、環の既約元の概念(一部の環では素元の概念と一致する)に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。 現代の定義では 1 は素数ではない。歴史を通しても 1 を素数に含めない数学者が多数派であったが、20世紀初頭の環論の成熟まで定義は統一されていなかった[7]。プラトンやアリストテレスを含むほとんどの古代ギリシアの哲学者は 1 を数とさえ見なさず[8][9]、素数性の考察の対象としなかった。スペウシッポスは 1 を数と見なし素数としたが、当時としては異端であった[10]。この時代には素数を奇数の一部分と考え、2 を素数に含めない数学者もいた(ただしユークリッドをはじめとする多数派は 2 を素数に含めている)。アラビアではおおむね古代ギリシアに倣って 1 は数でないとされた[8]。中世からルネサンスにかけて、1 が数として扱われるようになり、1 を最初の素数とする数学者も現れた[11]。18世紀半ば、ゴールドバッハはオイラーに宛てた書簡で 1 を素数に挙げている(ただしオイラー自身は 1 を素数とは考えていなかった)[12]。19世紀にも少数派だが 1 を素数に含める数学者はかなりいた[7]。ハーディの『A Course of Pure Mathematics』では、1933年に出版された第6版までは 1 を素数に含めているが、1938年の第7版から 2 を最小の素数とするよう改訂されている。レーマー
定義と例
02300050070000
11131719
2329
3137
414347
5359
6167
717379
8389
97
4以上の偶数。(2で割り切れる)
10以上で末尾が5か0の数。(5で割り切れる)
6以上で、数字根が3, 6, 9となる数(3で割り切れる)。(20以上では、21, 27, 33, 39, 51, 57, 63, 69, 81, 87, 93, 99, …)
一の位から見て奇数番目の位の数の和と、偶数番目の位の数の和との差が11の倍数であれば、11の倍数である(11で割り切れる)。(100以上では、110, 121, 132, 143, 154, 165, 176, 187, 198, 209, …)[5]
素因数分解の可能性・一意性詳細は「算術の基本定理」を参照
1 は素数か
1 も素数と定義すると、素数に関する多くの定理で、もとの「素数」を「1 以外の素数」と呼び替える記述の修正が必要になる。例えば 6 の素因数分解は、(積の順序を除いても)6 = 2 × 3 = 1 × 2 × 3 = 12 × 2 × 3 = 13 × 2 × 3 =…
と無数に与えられることになり、一意性は「1 を含む素数」については成り立たない[7]。エラトステネスの篩においては、1 も素数とすると、1 の倍数(すなわち他のすべての数)を消去し、残った唯一の数 1 を出力するので機能しない[15]。