素数

出典: フリー百科事典『ウィキペディア（Wikipedia）』
2014年7月3日 (木) 21:04時点における神奈川エーフレッツ (トーク)による版 (→‎語呂合わせ)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内、 検索
曖昧さ回避 化粧品会社については「素数 (企業)」をご覧ください。

素数（そすう、テンプレート:Lang-en-short）とは、1 と自分自身以外に正の約数を持たない自然数で、1 でない数のことである。正の約数の個数が 2 である自然数と言い換えることもできる。もし 1 を素数の定義に含めたとすると、算術の基本定理（素因数分解の可能性・一意性、すなわち「1 でない自然数は、素数の積に、素因数の順序を除いて一意に表される」を述べた定理）において、素因数分解の可能性は成り立つが一意性は成り立たなくなるということが起きてしまう。そのため、1 は素数の定義から除外するのが一般的である。

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

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

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

定義と例

100までの素数
テンプレート:02 3 テンプレート:0テンプレート:0 テンプレート:05 テンプレート:0テンプレート:0 7 テンプレート:0テンプレート:0 テンプレート:0テンプレート:0
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 以上の自然数を合成数と呼ぶ。

100以下の素数は、小さい順に次のようになる。

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（テンプレート:OEIS）

さらに、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

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

テンプレート:Main 「2 以上の自然数は、素数の積で表せる。その表し方は積の順序を除けば一意である」という、素因数分解の可能性・一意性が成立する（算術の基本定理）。すなわち、1 と「素数全体」の成す集合は、自然数全体の成す集合の（乗法に関する）最小の生成系である。俗な表現をすると、これは「1 と素数は自然数の構成要素である」などとなる。

素数の定義である「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]。

歴史

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

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

素数の個数

テンプレート:Main

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

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

ユークリッドによる証明

背理法による証明
素数が有限個（n 個とする）しかないと仮定し、i 番目の素数を pi とする。
q = p1p2 ... pn + 1
を考えよう。
q は有限個の自然数の積に 1 を加えた数なので自然数である。ゆえに、q は素数または合成数のどちらかである。
q は最大素数 pn より大きいので、素数でない。
したがって、q は合成数であることになる。すなわち、q はいくつかの pi の積である。すなわち、q をある pi で割った余りは 0 である。これは q の定義（pi で割った余りは 1）に矛盾。（証明終）

他の証明

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

  • 自然数の逆数の和が無限大に発散することを利用した証明[9]
  • 2つの異なるフェルマー数が互いに素であることを利用した証明[10]
  • 整数の集合に、等差数列の族を開基とする位相を入れる証明[11]
  • n ≥ 2 に対して、n(n + 1) は少なくとも相異なる2個の素因数を持つことを利用した証明[12]。おそらく最も短い。

素数判定と素因数分解

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

分布

ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。素数のない、いくらでも長い区間が存在する。例えば、n ≥ 2 に対して、連続する n − 1 個の自然数 n! + 2, …, n! + n はそれぞれ、より小さい 2, …, n で割り切れるので、どれも素数でない。また、比較的小さな数では、114 から 126 まで13個連続で合成数である。

これに関して、次の素数定理は有名である。この定理は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 未満」とも言い換えられる。したがって、現在知られている最大の素数 257885161 − 1 の次の素数は 257885162 − 2 未満である。

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

素数に関連する主な性質

素数の逆数和

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

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

エルデシュによる証明

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

<math>\sum_{i=N+1}^\infty \frac{1}{p_i} <\frac{1}{2} \cdots (1)</math>

を満たす N が存在する。

1, 2, …, n のうち最大素因数が pN 以下の自然数からなる集合を Mn とする。任意の k ∈ Mn に対して、

k = u2v（v の各素因数の指数は全て 1）

と表示すると、v は高々 2N 通り、u2 ≤ k ≤ n より

#Mn ≤ 2N√n …(2)

Mnc の元は少なくとも pN+1, pN+2, ... いずれかの倍数だから、(1) より

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

#Mnc = n − #Mn より

テンプレート:Sfrac < #Mn …(3)

(2), (3) より テンプレート:Sfrac < 2N √n, ∴ n < 22N+2。これは n の任意性に矛盾。（証明終）

その他の性質

素数生成式

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

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

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

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

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

と、p17 = 59 で割り切れてしまう（最小の反例）。

特殊な形をした素数

未解決問題

応用

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

公開鍵暗号

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

自然界の素数

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

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

語呂合わせ

整数の平方根や円周率などのように、素数にも語呂合わせによる記憶術がある。以下に挙げる。

2桁の素数

兄さん 5時に セブンイレブン 父さん いいなと ついていく 兄さん 買った肉を 裂いて みんなで食べたら 41円しか 予算がない
(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

37未満まで

兄さん 5時に セブンイレブン 父さん いないけれど 行く 兄さん 肉持って サーティーワン
(2, 3) 5 (7, 11) 13 17 19 23 29 31

脚注

テンプレート:脚注ヘルプ テンプレート:Reflist

参考文献

  • 本橋洋一，解析的整数論 I -- 素数分布論 --，朝倉書店，東京 2009（第２刷 2012: 加筆含む）ISBN 978-4-254-11821-6
  • 日本数学会市民講演　”素数の翼に乗って”　http://mathsoc.jp/publication/tushin/1001/motohashi.pdf
  • P. Ribenboim, "The Little Book of Bigger Primes", 2nd edition, Springer, 2004. ISBN 0-387-20169-6
    • 日本語訳、吾郷孝視『素数の世界』第2版、共立出版、2001年 ISBN 4-320-01684-X
  • M. Aigner and G. M. Ziegler, "Proofs from the Book", 3rd edition, Springer, 2003. ISBN 3-540-40460-0
    • 日本語訳、蟹江幸博『天書の証明』シュプリンガー・フェアラーク東京、2002年 ISBN 4-431-70986-X
  • M.R.シュレーダ『数論（上）』平野浩太郎、野村孝徳　訳、コロナ社、1995年、33～68頁ISBN 4-339-08216-3

関連項目

外部リンク

テンプレート:Link GA

テンプレート:Link GA
  1. ↑ The Prime Pages, The Top Ten Record Primes
  2. ↑ 例えば David E. Joyce's のユークリッド原論についてのコメンタリー Book VII, definitions 1 and 2 を参照。
  3. ↑ テンプレート:Harvard citations
  4. ↑ テンプレート:Harvard citations
  5. ↑ テンプレート:Citation
  6. ↑ "Arguments for and against the primality of 1".
  7. ↑ "Why is the number one not prime?"
  8. ↑ 日本語訳、中村幸四郎、寺阪英孝、池田美恵、伊東俊太郎『ユークリッド原論』共立出版 ISBN 4-320-01513-4
  9. ↑ レオンハルト・オイラーによる。現代的な用語で言えば、リーマンのゼータ関数のオイラー積表示を用いる。Ribenboim の第1章参照。
  10. ↑ ジョージ・ポーヤによる。Ribenboim の第1章または "Proof from the Book" の第1章を参照。
  11. ↑ ヒレル・ファステンバーグによる。en:Furstenberg's proof of the infinitude of primesを参照。
  12. ↑ テンプレート:Doi http://primes.utm.edu/notes/proofs/infinite/Saidak.html
  13. ↑ "Proofs from the Book" 第1章を参照。原論文は P. Erdös, "Über die Reihe ∑ 1/p", Mathematica, Zutphen B 7（1938), 1-2.
  14. ↑ Ribenboim 第3章
  15. ↑ 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
  16. ↑ テンプレート:Cite book
「http://wikippe.e-do-match.com/index.php?title=素数&oldid=5787」から取得