素数(そすう、英: 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 と自分自身でしか割り切れない」という条件(既約性)は、抽象代数学において、環の既約元の概念(一部の環では素元の概念と一致する)に抽象化され一般的に取り扱われる。
定義と例
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]
素因数分解の可能性・一意性詳細は「算術の基本定理」を参照