素数
自然数で素数でないものが連続している区間を「素数砂漠」という。例えば{24, 25, 26, 27, 28} は「長さ 5 の素数砂漠」である。素数砂漠を挟む2個の素数は 3 以上であるため、共に奇数である。このことから、素数砂漠の長さは必ず奇数である。いくらでも長い素数砂漠が構成できる(#分布を参照)。
初めから60個の素数の間隔は
1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 6, 4, 6, 6, 2, 10, 2, 4, 2, 12, 12, 4, 2, 4, 6, 2, 10, 6, 6, 6, 2, 6, 4, 2, ...
(a, m) = 1 のとき、等差数列:a, a + m, a + 2m, ... には素数の項が無数に含まれている。(ディリクレの算術級数定理)
ここで m = 10 とすると、十進表記において一の位が 1, 3, 7, 9 である素数はどれも無数にあることが分かる。
素数 p に対して、(a, p) = 1 ⇒ a ≡ 1 (mod p)(フェルマーの小定理)
p が素数 ⇔ (p − 1)! ≡ −1 (mod p)(ウィルソンの定理)
素数の2乗差は 5 の倍数, 3 の倍数, 8 の倍数のいずれかである。
5 ( = 3 − 2), 16 ( = 5 − 3), 21 ( = 5 − 2), 24 ( = 7 − 5), 40 ( = 7 − 3), ...
約数の和が素数になる自然数は、2 と素数かその累乗数の平方数である。しかし、素数やその累乗数の自乗であっても約数の和が素数になるとは限らない。約数の和が素数になる数が無限にあるかどうかの証明はされていない(後述)。
七進表記において、5以上の素数の数字根は、必ず1か5となる。
公開鍵暗号のアルゴリズムとして、RSA暗号やディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの(大きな)素数の掛け算は比較的簡単に(効率的に)行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。
「2 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する(算術の基本定理)。素因数分解の可能性から、素数全体の成す集合は、2以上の自然数全体の成す集合とその乗法からなる半群の最小の生成系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる。
素数の定義である「1 と自分自身でしか割り切れない」という条件(既約性)は、抽象代数学において、環の既約元の概念(一部の環では素元の概念と一致する)に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。