素数
定められた素数の個数が n 個であるとき、n 個の素数を小さい順番に並べて i 番目の素数を pi とする。
1 < p1 < p2 < ... < pn.
このとき、n 個の素数をすべて掛け合わせた数に 1 を加えた数を q とすると、
q = p1 × p2 × ... × pn + 1.
q は有限個の自然数の積に 1 を加えた数なので 1 より大きい自然数である。ゆえに、q は素数または合成数のどちらかである。
q が素数のとき、q は最大の素数 pn より大きい素数になるので、定められた個数の素数よりも多くの素数が存在する。
q が合成数のとき、q を割り切る素数が存在する。一方、q の定義より、すべての pi で割った余りは 1 になるので、q はすべての pi で割り切れない。したがって、すべての pi 以外に素数が存在する。すなわち、定められた個数の素数よりも多くの素数が存在する。(証明終)
紀元前1600年頃のエジプト第2中間期において、素数の初等的な性質が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや、その他の素数の性質が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩は、素数を列挙するための計算方法である。
古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を(未証明ではあるが)述べた。この定理は後にライプニッツとオイラーによって証明された。
素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論』の中で証明している。
レーマー(英語版)の 1 を含む素数表は1956年まで出版された。ルベーグは 1 を素数だと考えた最後の専門的な数学者だと言われている。
1 も素数と定義すると、素数に関する多くの定理で、もとの「素数」を「1 以外の素数」と呼び替える記述の修正が必要になる。例えば 6 の素因数分解は、(積の順序を除いても)
6 = 2 × 3 = 1 × 2 × 3 = 1 × 2 × 3 = 1 × 2 × 3 =...
と無数に与えられることになり、一意性は「1 を含む素数」については成り立たない。エラトステネスの篩においては、1 も素数とすると、1 の倍数(すなわち他のすべての数)を消去し、残った唯一の数 1 を出力するので機能しない。さらに、1 以外の素数で成り立つ様々な性質がある(例えば、自然数とそれに対応するオイラーのφ関数や約数関数の値との関係など)。20世紀初頭までに 1 は素数ではなく「単数」という特別な分類に属するという見方が一般的になった。