素数
次のような定理もある。
「任意の自然数 n に対して、n < p ≤ 2n を満たす素数 p が存在する」(ベルトランの仮説、チェビシェフの定理)
この主張は「任意の素数 p の次の素数は 2p 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 2 − 1 の次の素数は 2 − 2 未満である。
一方で、例えば n と (n + 1) の間に素数が存在するかという問題は未解決である(ルジャンドル予想)。
素数が全く無い区間は、いくらでも長いものがあることが知られている。n ≥ 2 に対して、連続する n − 1 個の自然数 n! + 2, ..., n! + n はそれぞれ、それらより小さい 2, ..., n で割り切れるので、どれも素数でない。n は任意にとれるから、素数が全く無いいくらでも長い区間があると言える。これは一例にすぎず、実際にはもっと小さい所で、素数が全く無い長い区間が生じるようである。例えば、114 から 126 まで13個連続で合成数である。
素数とは、自明な正の因数(1 と自分自身)以外に因数を持たない自然数であり、1 でない数のことである。つまり、正の因数の個数が 2 である自然数である。
例えば、2 は、正の因数が 1, 2 のみなので素数である。
素数でない 2 以上の自然数を合成数と呼ぶ。
合成数であることの判定法として、たとえば下記の4条件がある:
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, ...)
逆に、この4条件を、全て満たさない数でも素数とは限らない。例えば、91 は、正の因数が 1, 7, 13, 91 なので素数ではない。
また、2, 3 以外の素数は、最も近い6の倍数との差が 1 か −1 である。
2 でない素数は奇数であり、奇素数と呼ぶ。
100以下の素数は25個存在し、小さい順に次の通りである。
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
さらに、1000以下の素数は100以下のものを含め168個存在する(100以下を除けば143個)。
n番目の素数を求める素数生成式は存在しないと主張されることがあるが、これは誤りである(ウィルソンの定理やミルズの定理(英語版)を用いたものが存在する)。しかしながら、そのような式で実効的に計算可能(英語版)なものは知られていない。
以下は1964年に Willans C.P. が報告したウィルソンの定理に基づく公式で、n番目の素数 pn を求めることができる:
p ( n ) = 1 + ∑ m = 1 2 n ⌊ n ∑ k = 1 m ⌊ cos 2  ( k − 1 ) ! + 1 k π ⌋ n ⌋ {\displaystyle p(n)=1+\textstyle \sum \limits _{m=1}^{2^{n}}\left\lfloor {\sqrt[{n}]{\dfrac {n}{\sum \limits _{k=1}^{m}\left\lfloor \cos ^{2}{\frac {\left(k-1\right)!+1}{k}}\pi \right\rfloor }}}\right\rfloor }