素数
素数の逆数和は収束すると仮定する。i 番目の素数を pi で表すと、
∑ i = N + 1 ∞ 1 p i < 1 2 ⋯ ( 1 ) {\displaystyle \sum _{i=N+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {1}{2}}\cdots (1)}
を満たす N が存在する。
n 以下の自然数のうち最大素因数が pN 以下のものからなる集合を An とする。任意の k ∈ An に対して、
k = uv(v の各素因数の指数は全て 1)
と表示すると、v は高々 2 通り、u ≤ k ≤ n より
#An ≤ 2√n ...(2)
An の元は、pN+1 以上の素因数を少なくとも1つ持つから、(1) より
# A n c ≤ ∑ i = N + 1 ∞ [ n p i ] ≤ n ∑ i = N + 1 ∞ 1 p i < n 2 {\displaystyle \#{A_{n}}^{c}\leq \sum _{i=N+1}^{\infty }\left[{\frac {n}{p_{i}}}\right]\leq n\sum _{i=N+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {n}{2}}}
#An = n − #An より
n/2 < #An ...(3)
(2), (3) より n/2 < 2 √n, ∴ n < 2。これは n の任意性に矛盾。(証明終)
双子素数に限ると、逆数和は B2 = 1.902... に収束することが証明されている(ブルン定数)。
エラトステネスの篩
ウラムの螺旋
プリヒタの素数円
素数が無数に存在することは、紀元前3世紀頃のエウクレイデス(以下ユークリッド)の著書『原論』で既に証明されていた。そこでの証明は、背理法により次のようになる:
『素数全体は有限個と仮定して、全ての素数の総乗に1を足した数をNとする。Nはどの素数で割っても余りが1となる。一方、Nはどの素数よりも大きいので、Nは素数ではない。すなわち、Nはある素数で割り切れる。これは、Nを整数で割った余りが一意であることに矛盾する。ゆえに、素数は無数にある。』
自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。
分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2021年4月現在で知られている最大の素数は、2018年12月7日に発見された、それまでに分かっている中で51番目のメルセンヌ素数 2 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ。