素数

提供: miniwiki
2018/9/29/ (土) 21:04時点におけるAdmin (トーク | 投稿記録)による版 (語呂合わせ)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先:案内検索

素数(そすう、: prime number)とは、1 より大きい自然数で、正の約数1 と自分自身のみであるもののことである。正の約数の個数が 2 である自然数と言い換えることもできる。1 より大きい自然数で素数でないものは合成数と呼ばれる。

一般には、素数は代数体の整数環の素元として定義される(そこでは反数などの同伴なものも素数に含まれる)。このため、有理整数環 [math]\mathbb Z[/math] での素数は有理素数(ゆうりそすう、: rational prime)と呼ばれることもある。

最小の素数は 2 である。素数は無数に存在する。したがって、素数からなる無限数列が得られる。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, …オンライン整数列大辞典の数列 A40

素数が無数に存在することは、紀元前3世紀頃のユークリッドの著書『原論』で既に証明されていた。

自然数あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想などの現代数学の重要な問題との興味深い結び付きが発見されている。

分散コンピューティング・プロジェクト GIMPS により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、2017年12月に発見された、それまでに分かっている中で50番目のメルセンヌ素数 277232917 − 1 であり、十進法で表記したときの桁数は2324万9425桁に及ぶ[1]

定義と例

100 以下の素数一覧
02 3 00 05 00 7 00 00
11 13 17 19
23 29
31 37
41 43 47
53 59
61 67
71 73 79
83 89
97

素数とは、自明な正の約数(1 と自分自身)以外に約数を持たない自然数であり、1 でない数のことである。つまり、正の約数の個数が 2 である自然数のことである。例えば、2 は、正の約数が 1, 2 のみなので素数である。一方で 91 は、正の約数が 1, 7, 13, 91 なので素数でない。素数でない 2 以上の自然数を合成数と呼ぶ。また、特に 2 でない素数は奇数であり、奇素数と呼ぶ。十進法表示では、2, 5 以外の素数は、一の位が 1, 3, 7, 9 のいずれかである。

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オンライン整数列大辞典の数列 A40

さらに、1000以下の素数は100以下のものを含め168個存在する。101以上の1000以下の素数は小さい順に次の通りである。

101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

素因数分解の可能性・一意性

2 以上の自然数は、素数ので表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する(算術の基本定理)。すなわち、「素数全体」の成す集合は、自然数全体の成す集合の(乗法に関する)最小の生成系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる。

素数の定義である「1 と自分自身でしか割り切れない」という条件(既約性)は、抽象代数学において、既約元の概念(一部の環では素元の概念と一致する)に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えばネーター環では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。

1 は素数か

素数の定義を「自明でない(1 と自分自身以外)約数の積に分解できない自然数」と考えた場合、「1 を素数の定義に含めるか含めないか」が問題となる。古代ギリシアでは、1 はそもそも数(自然数)であるとさえ見なされなかった[2]ので、1 は素数ではなかった。一方、19世紀には、1 は素数であると考える数学者が多く存在した。例えば、レーマー10,006,721 までの素数表(後の1956年に再版[3])では、素数は 1 から始まるものとして書かれている[4]アンリ・ルベーグは、1 を素数だと考えた最後の専門的な数学者だと言われている[5]

1 は素数であると仮定しても、素因数分解の可能性は成り立ち、数学の大部分の命題ではそのままの文面で変わらず有効であるが、素因数分解の一意性は成り立たなくなる。1 が素数だとすると、例えば 6 の素因数分解は、(積の順序を除いても)

6 = 2 × 3 = 1 × 2 × 3 = 12 × 2 × 3 = …

と無数の素因数分解を与えることになり、一意性が成り立たなくなる。さらに、1 以外の素数で成り立つ様々な性質がある(例えば、自然数とそれに対応するオイラーのφ関数約数関数の値との関係など)[6][7]

歴史

紀元前1600年頃のエジプト第2中間期において、素数に関する知識が部分的に知られていたことが、リンド数学パピルスなどの資料によって示唆されている。例えば分数をエジプト式分数で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは古代ギリシア人が最初である。紀元前約300年頃に書かれたユークリッドの『原論』には素数が無数に存在することや、その他の素数の性質が証明されている。また、ユークリッドはメルセンヌ素数から完全数を構成する方法を示している。ギリシアの数学者、エラトステネスに因んで名付けられたエラトステネスの篩(ふるい)は、素数を列挙するための計算方法である。

古代ギリシア時代の後、17世紀になるまで素数の研究にはそれほどの進展が無かった。1640年に、ピエール・ド・フェルマーはフェルマーの小定理を(未証明ではあるが)述べた。この定理は後にライプニッツオイラーによって証明された。

素数の個数

ファイル:Ulam 1.png
自然数を渦巻状に並べていき、素数だけを黒く塗ったもの(ウラムの螺旋)。
素数が高密度に集まった対角線、水平線、垂線が見て取れる。素数の分布が極めて難解であるために、この素数のパターンが示す事実については未だに明らかにされていない。

素数が無数に存在することは既に古代ギリシア時代から知られていて、ユークリッドが彼の著作『原論[8]の中で証明している。

ユークリッドによる証明

『原論』第9巻 命題20[8]
素数の個数はいかなる定められた素数の個数よりも多い。
定められた個数の素数を p1, p2, …, pn とせよ。p1, p2, …, pn より多い個数の素数があると主張する。
『原論』による証明[注釈 1]
定められた素数の個数が 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 以外に素数が存在する。すなわち、定められた個数の素数よりも多くの素数が存在する。(証明終
自然数の有限集合 A の全ての要素を掛け合わせた自然数を f(A) とする。
定められた個数の素数から成る集合を A3 = {2, 3, 5} とするとき、f(A3) = 2 × 3 × 5 + 1 = 31 は素数なので、新しい素数 31 が得られる。したがって、定められた個数より多くの素数が存在する。
定められた個数の素数から成る集合を A4 = {2, 3, 5, 31} とするとき、f(A4) = 2 × 3 × 5 × 31 + 1 = 931 = 7 × 7 × 19 なので、新しい素数 719 が得られる。したがって、定められた個数より多くの素数が存在する。

他の証明

上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。

素数判定と素因数分解

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

分布

ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。素数のない、いくらでも長い区間が存在する。例えば、n ≥ 2 に対して、連続する n − 1 個の自然数 n! + 2, …, n! + n はそれぞれ、より小さい 2, …, n で割り切れるので、どれも素数でない。また、比較的小さな数では、114 から 126 まで13個連続で合成数である。(この区間の最初の値はオンライン整数列大辞典の数列 A008950を、終了の値はオンライン整数列大辞典の数列 A008995をその区間幅についてはオンライン整数列大辞典の数列 A008996を参照)

これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。

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

[math]\pi (x)\sim \int_2^x \frac{dt}{\log t} \sim \frac{x}{\log x}\quad (x\to \infty)[/math]

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

次のような定理もある。

「任意の自然数 n に対して、n < p ≤ 2n を満たす素数 p が存在する」(ベルトランの仮説チェビシェフの定理)

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

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

素数計数

2015年に、ゴールドバッハの予想検証プロジェクトは 4 × 1018 以下の全ての素数(9京5676兆2609億388万7607個、約 1017個)を計算したと報告した[12][13]が、結果は保存されていない。しかしながら、素数計数関数を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、1023 以下に 19垓2532京391兆6068億396万8923個(約 2×10{{#invoke:Gapnum|main|21}}個)の素数があると計算された。

また、別の計算によると、リーマン予想が真であると仮定した場合、1024 以下に 184垓3559京9767兆3492億86万7866個(約 2×10{{#invoke:Gapnum|main|22}}個) の素数が存在する[14]

分布の視覚化

素数に関連する主な性質

素数の逆数和

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

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

エルデシュによる証明

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

[math]\sum_{i=N+1}^\infty \frac{1}{p_i} \lt \frac{1}{2} \cdots (1)[/math]

を満たす N が存在する。

n 以下の自然数のうち最大素因数が pN 以下のものからなる集合を An とする。任意の kAn に対して、

k = u2vv の各素因数の指数は全て 1

と表示すると、v は高々 2N 通り、u2kn より

#An ≤ 2Nn …(2)

Anc の元は、pN+1 以上の素因数を少なくとも1つ持つから、(1) より

[math]\# {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} \lt \frac{n}{2}[/math]

#Anc = n − #An より

n/2 < #An …(3)

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

双子素数に限ると、逆数和は B2 = 1.902… に収束することが証明されている(ブルン定数)。

その他の性質

5 ( = 32 − 22), 16 ( = 52 − 32), 21 ( = 52 − 22), 24 ( = 72 − 52), 40 ( = 72 − 32), …

素数生成式

オイラーの発見した式、f(n) = n2 + n + 41 は、n = 0, …, 39 で全て素数となる。これは、虚二次体 [math]\mathbb{Q}(\sqrt{-163})[/math]類数1 であることと関係している[15][16][17]

多変数の高次多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、k + 2 が素数となる必要十分条件は、次のディオファントス方程式が自然数解を持つことである[18]:

wz + h + j − q = 0
(gk + 2g + k + 1)(h + j) + hz = 0
(16k + 1)3(k + 2)(n + 1)2 + 1 − f2 = 0
2n + p + q + ze = 0
e3(e + 2)(a + 1)2 + 1 − o2 = 0
(a2 − 1)y2 + 1 − x2 = 0
16r2y4(a2 − 1) + 1 − u2 = 0
n + l + vy = 0
(a2 − 1)l2 + 1 − m2 = 0
ai + k + 1 − li = 0
[{a + u2(u2a)}2 − 1](n + 4dy)2 + 1 − (x + cu)2 = 0
p + l(an − 1) + b(2an + 2an2 − 2n − 2) − m = 0
q + y(ap − 1) + s(2ap + 2ap2 − 2p − 2) − x = 0
z + pl(ap) + t(2app2 − 1) − pm = 0

誤解されやすいが、素数が無数に存在することの、#ユークリッドによる証明で使われる手順からは、必ずしも素数を得ることができない。なぜなら最初の仮定「最大の素数 pn が存在する」が正しくないからである。実際に、n = 6

2 × 3 × 5 × 7 × 11 × 13 + 1 = 30031 = 59 × 509

と、自明でない約数に分解できてしまう(最小の反例)。

特殊な形をした素数

未解決問題

応用

長い間、数論、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者であるハーディは、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数はハッシュテーブル擬似乱数生成にも用いられ、工学的応用上重要度の高いものとなっている。

公開鍵暗号

公開鍵暗号のアルゴリズムとして、RSA暗号ディフィー・ヘルマン鍵共有といった、大きな数の素因数分解は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの(大きな)素数の掛け算は比較的簡単に(効率的に)行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。

自然界の素数

自然界に現れる素数の一例として、素数ゼミと呼ばれるセミの一種がいる。アメリカ合衆国に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がズレてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる[22]

また、ゼータ関数上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。

連続素数

連続素数和

連続数 参照 含まれる素数列
2
5, 8, 12, 18, 24, 30, 36, 42, 52, 60, 68, 78, 84, … オンライン整数列大辞典の数列 A001043
3
10, 15, 23, 31, 41, 49, 59, 71, 83, 97, 109, … オンライン整数列大辞典の数列 A034961 オンライン整数列大辞典の数列 A034962
4
17, 26, 36, 48, 60, 72, 88, 102, 120, 138, 152, … オンライン整数列大辞典の数列 A034963
5
28, 39, 53, 67, 83, 101, 119, 139, 161, 181, … オンライン整数列大辞典の数列 A034964 オンライン整数列大辞典の数列 A034965
6
41, 56, 72, 90, 112, 132, 156, 180, 204, 228, … オンライン整数列大辞典の数列 A127333
7
58, 75, 95, 119, 143, 169, 197, 223, 251, 281, … オンライン整数列大辞典の数列 A127334 オンライン整数列大辞典の数列 A082246
8
77, 98, 124, 150, 180, 210, 240, 270, 304, … オンライン整数列大辞典の数列 A127335
9
100, 127, 155, 187, 221, 253, 287, 323, 363, … オンライン整数列大辞典の数列 A127336 オンライン整数列大辞典の数列 A082251
10
129, 158, 192, 228, 264, 300, 340, 382, 424, … オンライン整数列大辞典の数列 A127337
11
160, 195, 233, 271, 311, 353, 399, 443, 491, … オンライン整数列大辞典の数列 A127338 オンライン整数列大辞典の数列 A127340
12
197, 236, 276, 318, 364, 412, 460, 510, 562, … オンライン整数列大辞典の数列 A127339
13
238, 279, 323, 371, 423, 473, 527, … オンライン整数列大辞典の数列 A127341

連続素数積

連続数 参照
2
6, 15, 35, 77, 143, 221, 323, 437, 667, 899, 1147, 1517, 1763, … オンライン整数列大辞典の数列 A006094
3
30, 105, 385, 1001, 2431, 4199, 7429, 12673, 20677, 33263, 47027, … オンライン整数列大辞典の数列 A046301
4
210, 1155, 5005, 17017, 46189, 96577, 215441, 392863, 765049, … オンライン整数列大辞典の数列 A046302
5
2310, 15015, 85085, 323323, 1062347, 2800733, … オンライン整数列大辞典の数列 A046303
6
30030, 255255, 1616615, 7436429, 30808063, 86822723, … オンライン整数列大辞典の数列 A046324
7
510510, 4849845, … オンライン整数列大辞典の数列 A046325
8
9699690, 111546435, … オンライン整数列大辞典の数列 A046326
9
223092870, 3234846615, … オンライン整数列大辞典の数列 A046327
10
6469693230, 100280245065, … オンライン整数列大辞典の数列 A127342
11
200560490130, 3710369067405, … オンライン整数列大辞典の数列 A127343
12
7420738134810, 152125131763605, … オンライン整数列大辞典の数列 A127344

脚注

注釈

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

出典

  1. The Prime Pages, The Top Ten Record Primes
  2. 例えば David E. Joyce's のユークリッド原論についてのコメンタリー Book VII, definitions 1 and 2 を参照。
  3. Riesel 1994, p. 36
  4. Conway & Guy 1996, pp. 129f
  5. Derbyshire 2003, p. 33
  6. "Arguments for and against the primality of 1".
  7. "Why is the number one not prime?"
  8. 8.0 8.1 ユークリッド 2011, 9-20
  9. 9.0 9.1 Ribenboim 2001, 第1章
  10. 10.0 10.1 アイグナー & ツィーグラー 2012, 第1章
  11. doi:10.2307/27642094 http://primes.utm.edu/notes/proofs/infinite/Saidak.html
  12. Tomás Oliveira e Silva, Goldbach conjecture verification. Retrieved 16 July 2013.
  13. オンライン整数列大辞典の数列 A080127
  14. Jens Franke (2010年7月29日). “Conditional Calculation of pi(1024)”. . 2015閲覧.
  15. Ribenboim 2001, 第3章
  16. オンライン整数列大辞典の数列 A005486
  17. オンライン整数列大辞典の数列 A202018
  18. Jones, James P.; Sato, Daihachiro; Wada, Hideo; Wiens, Douglas (1976), "Diophantine representation of the set of prime numbers", American Mathematical Monthly 83: 449–464, doi:10.2307/2318339
  19. Helfgott, H.A. (2013年). “Major arcs for Goldbach's theorem”. arXiv:1305.2897 [math.NT]. 
  20. Helfgott, H.A. (2012年). “Minor arcs for Goldbach's problem”. arXiv:1205.5252/ [math.NT]. 
  21. http://www.humboldt-professur.de/en/preistraeger/preistraeger-2015/harald-andres-helfgott
  22. 吉村 2008

参考文献

関連項目

外部リンク

|CitationClass=citation }}