素数(そすう)の意味や定義わかりやすく解説 Weblio辞書

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

素数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/30 02:13 UTC 版)

素数判定と素因数分解

詳細は「素数判定」および「素因数分解」を参照

与えられた自然数 $n$ が素数であるか合成数であるかを判定するためのアルゴリズムが多数考案されている。最も素朴な方法は、 $2$ から $\sqrt n$ 以下の素数まで順番に割っていく、試し割り法と呼ばれる方法である。 $n$ が $\sqrt n$ 以下の全ての素数で割り切れなければ $n$ は素数である。試し割り法は、 $n$ が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割り法よりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。

上記の通り2を除く偶数、2桁以上で末尾が5の数、数字和が3の倍数となる数は合成数と分かるのでそれを省き、7以上の素数を順番に割る方法がある。

分布

ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。

$x$ 以下の素数の個数を $π (x)$ （素数計数関数）とすると、

\pi (x)\sim \int _{2}^{x}{\frac {dt}{\log t}}\sim {\frac {x}{\log x}}\quad (x\to \infty )

が成り立つ。この定理は、1792年に15歳のカール・フリードリヒ・ガウスによって予想されていた（ガウスが最初に予想したのかどうかは不明）。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。

次のような定理もある。

「任意の自然数

n

に対して、

n < p \leq 2 n

を満たす素数

p

が存在する」（ベルトランの仮説、チェビシェフの定理）

この主張は「任意の素数 $p$ の次の素数は $2 p$ 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 $282589933 - 1$ の次の素数は $282589934 - 2$ 未満である。

一方で、例えば $n 2$ と $(n + 1) 2$ の間に素数が存在するかという問題は未解決である（ルジャンドル予想）。

素数が全く無い区間は、いくらでも長いものがあることが知られている。 $n \geq 2$ に対して、連続する $n - 1$ 個の自然数 $n! + 2, \dots, n! + n$ はそれぞれ、それらより小さい $2, \dots, n$ で割り切れるので、どれも素数でない。 $n$ は任意にとれるから、素数が全く無いいくらでも長い区間があると言える。これは一例にすぎず、実際にはもっと小さい所で、素数が全く無い長い区間が生じるようである。例えば、 $114$ から $126$ まで $13$ 個連続で合成数である^[23]。

素数計数

2015年に、ゴールドバッハの予想検証プロジェクトは $4 \times 10 18$ 以下の全ての素数（9京5676兆2609億0388万7607個、約 10¹⁷個）を計算したと報告した^[24]が、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、 $1023$ 以下に 19垓2532京0391兆6068億0396万8923個（約 2×10²¹個）の素数があると計算された。

また、別の計算によると、リーマン予想が真であると仮定した場合、 $1024$ 以下に 184垓3559京9767兆3492億0086万7866個（約 2×10²²個）の素数が存在する^[25]。

分布の視覚化

素数に関連する主な性質

素数の逆数和

素数の逆数の和は（無限大に）発散する。この命題は『素数は無数に存在する』という命題を含んでいる（有限個ならば収束、すなわち発散しないはずである）が、それだけではなく素数の分布に関してより多くの情報を提供している。

この結果は最初にレオンハルト・オイラーによりゼータ関数を研究することでもたらされた。以下の証明はポール・エルデシュによる、より直接的で、また簡潔な証明である^{[注釈 7]}。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。

エルデシュによる証明

素数の逆数和は収束すると仮定する。 $i$ 番目の素数を $p i$ で表すと、

\sum _{i=N+1}^{\infty }{\frac {1}{p_{i}}}<{\frac {1}{2}}\cdots (1)

を満たす $N$ が存在する。

$n$ 以下の自然数のうち最大素因数が $p N$ 以下のものからなる集合を $A n$ とする。任意の $k \in A n$ に対して、

k = u 2 v

（

v

の各素因数の指数は全て

1

）

と表示すると、 $v$ は高々 $2 N$ 通り、 $u 2 \leq k \leq n$ より

# A n \leq 2 N \sqrt n

…(2)

$A n c$ の元は、 $p N +1$ 以上の素因数を少なくとも1つ持つから、(1) より

\#{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}}

$# A n c = n - # A n$ より

n / 2 < # A n

…(3)

(2), (3) より $n / 2 < 2 N \sqrt n$ , ∴ $n < 2 2 N +2$ 。これは $n$ の任意性に矛盾。（証明終）

双子素数に限ると、逆数和は $B 2 = 1.902\dots$ に収束することが証明されている（ブルン定数）。

その他の性質

$(a, m) = 1$ のとき、等差数列： $a, a + m, a + 2 m, \dots$ には素数の項が無数に含まれている。（ディリクレの算術級数定理）

ここで

m = 10

とすると、十進表記において一の位が

1, 3, 7, 9

である素数はどれも無数にあることが分かる。

素数 $p$ に対して、 $(a, p) = 1 \Rightarrow a p -1 \equiv 1 (mod p)$ （フェルマーの小定理）
$p$ が素数 $\Leftrightarrow (p - 1)! \equiv -1 (mod p)$ （ウィルソンの定理）
素数の2乗差は $5$ の倍数, $3$ の倍数, $8$ の倍数のいずれかである。

5 ( = 3 2 - 2 2), 16 ( = 5 2 - 3 2), 21 ( = 5 2 - 2 2), 24 ( = 7 2 - 5 2), 40 ( = 7 2 - 3 2), \dots

約数の和が素数になる自然数は、 $2$ と素数かその累乗数の平方数である。しかし、素数やその累乗数の自乗であっても約数の和が素数になるとは限らない。約数の和が素数になる数が無限にあるかどうかの証明はされていない（後述）。
七進表記において、5以上の素数の数字根は、必ず1か5となる。

脚注

注釈

^ どの素数も他の自然数の積では表せないためこれ以上小さい生成系は存在しない。
^ ユークリッドによる証明では、変数・数式・任意の個数を示すパラメーター $n$ を使用せずに、定められた個数が 3個の素数 $Α, Β, Γ$ の場合に証明している。これを「準一般的」な証明という。詳細は素数が無数に存在することの証明#ユークリッドを参照。
^ レオンハルト・オイラーによる。現代的な用語で言えば、リーマンゼータ関数のオイラー積表示を用いる^[20]。
^ ジョージ・ポーヤによる^[20]^[21]。
^ ヒレル・ファステンバーグによる。en:Furstenberg's proof of the infinitude of primesを参照。
^ 素数が無数に存在することの証明#サイダックを参照^[22]。
^ 『天書の証明』第1章^[21]を参照。原論文は Erdös, P. (1938-07), “Über die Reihe ∑ 1/p” (German) (PDF), Mathematica, Zutphen B: 1-2 。