提供: miniwiki

← 素数

あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:

---

このページのソースの閲覧やコピーができます。

{{Otheruses||化粧品会社|素数 (企業)}} '''素数'''（そすう、{{lang-en-short|''prime number''}}）<!--読み方はプライムナンバー-->とは、{{math|1}} より大きい[[自然数]]で、正の[[約数]]が {{math|[[1]]}} と自分自身のみであるもののことである。正の約数の個数が {{math|2}} である自然数と言い換えることもできる。{{math|1}} より大きい自然数で素数でないものは[[合成数]]と呼ばれる。 一般には、素数は[[代数体]]の整数環の[[素元]]として定義される（そこでは[[反数]]などの[[整域#可除性、素元と既約元|同伴]]なものも素数に含まれる）。このため、[[整数|有理整数環]] <math>\mathbb Z</math> での素数は'''有理素数'''（ゆうりそすう、{{lang-en-short|''rational prime''}}）と呼ばれることもある。 最小の素数は {{math|[[2]]}} である。素数は無数に存在する。したがって、素数からなる無限[[数列]]が得られる。 :{{math2|[[2]], [[3]], [[5]], [[7]], [[11]], [[13]], [[17]], [[19]], [[23]], [[29]], [[31]], [[37]], [[41]], [[43]], [[47]], …}}（<!--50以下の素数、-->{{OEIS|id=A40}}） 素数が無数に存在することは、[[紀元前3世紀]]頃の[[エウクレイデス|ユークリッド]]の著書『[[ユークリッド原論|原論]]』で既に証明されていた。 [[自然数]]あるいは[[実数]]の中での素数の分布の様子は高度に非自明で、[[リーマン予想]]などの現代数学の重要な問題との興味深い結び付きが発見されている。 [[分散コンピューティング]]・プロジェクト [[GIMPS]] により、史上最大の素数の探求が行われている。2018年1月現在で知られている最大の素数は、[[2017年]][[12月]]<!--26日-->に発見された、それまでに分かっている中で50番目の[[メルセンヌ数|メルセンヌ素数]] {{math|2{{sup|77232917}} &minus; 1}} であり、[[十進法]]で表記したときの桁数は2324万9425桁に及ぶ<ref>The Prime Pages, [http://primes.utm.edu/largest.html#biggest The Top Ten Record Primes]</ref>。 == 定義と例 == {|class="wikitable" style="font-size:95%;text-align:right;float:right;margin:0px 0px 3px 7px;line-height:1.3em" !colspan="10"|{{math|[[100]]}} 以下の素数一覧 |- | ||{{0}}{{math|[[2]]}}||{{math|[[3]]}}||{{0}}{{0}}||{{0}}{{math|[[5]]}}||{{0}}{{0}}||{{math|[[7]]}}||{{0}}{{0}}|| ||{{0}}{{0}} |- |{{math|[[11]]}}|| ||{{math|[[13]]}}|| || || ||{{math|[[17]]}}|| ||{{math|[[19]]}}|| |- | || ||{{math|[[23]]}}|| || || || || ||{{math|[[29]]}}|| |- |{{math|[[31]]}}|| || || || || ||{{math|[[37]]}}|| || || |- |{{math|[[41]]}}|| ||{{math|[[43]]}}|| || || ||{{math|[[47]]}}|| || || |- | || ||{{math|[[53]]}}|| || || || || ||{{math|[[59]]}}|| |- |{{math|[[61]]}}|| || || || || ||{{math|[[67]]}}|| || || |- |{{math|[[71]]}}|| ||{{math|[[73]]}}|| || || || || ||{{math|[[79]]}}|| |- | || ||{{math|[[83]]}}|| || || || || ||{{math|[[89]]}}|| |- | || || || || || ||{{math|[[97]]}}|| || || |} 素数とは、自明な正の約数（{{math|1}} と自分自身）以外に約数を持たない自然数であり、{{math|1}} でない数のことである。つまり、正の約数の個数が 2 である自然数のことである。例えば、{{math|2}} は、正の約数が {{math|1, 2}} のみなので素数である。一方で {{math|[[91]]}} は、正の約数が {{math|1, 7, 13, 91}} なので素数でない。素数でない {{math|2}} 以上の自然数を'''[[合成数]]'''と呼ぶ。また、特に {{math|2}} でない素数は[[奇数]]であり、'''奇素数'''と呼ぶ。[[十進法]]表示では、{{math|2, 5}} 以外の素数は、一の位が {{math|1, 3, 7, 9}} のいずれかである。 100以下の素数は25個存在し、小さい順に次の通りである。 :{{math2|[[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|id=A40}}） さらに、1000以下の素数は100以下のものを含め168個存在する。101以上の1000以下の素数は小さい順に次の通りである。 :{{math2|[[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|算術の基本定理}} 「{{math|2}} 以上の自然数は、素数の[[積]]で表せる。その表し方は積の順序を除けば一意である」という、'''[[素因数分解]]'''の可能性・一意性が成立する（'''[[算術の基本定理]]'''）。すなわち、「素数全体」の成す集合は、自然数全体の成す集合の（乗法に関する）最小の[[生成 (数学)|生成]]系である。言い換えれば、これは「素数は自然数の構成要素である」などとなる。 素数の定義である「{{math|1}} と自分自身でしか割り切れない」という条件（既約性）は、[[抽象代数学]]において、[[環 (数学)|環]]の[[既約元]]の概念（一部の環では[[素元]]の概念と一致する）に抽象化され一般的に取り扱われる。一般の環で、任意の元は既約元の積に分解され、しかもその表示は一意であるという性質は稀有である。例えば[[ネーター環]]では、任意の元は既約元分解が可能であるが、その表示が一意ではないネーター環の例はいくつも知られている。一意に既約元分解ができる環は[[一意分解環]]と呼ばれ、既約元分解は素元分解ともなる。 === {{math|1}} は素数か === 素数の定義を「自明でない（{{math|1}} と自分自身以外）約数の積に分解できない自然数」と考えた場合、「{{math|1}} を素数の定義に含めるか含めないか」が問題となる。[[古代ギリシア]]では、{{math|1}} はそもそも数（自然数）であるとさえ見なされなかった<ref>例えば David E. Joyce's の[[ユークリッド原論]]についてのコメンタリー [http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/defVII1.html Book VII, definitions 1 and 2] を参照。</ref>ので、{{math|1}} は素数ではなかった。一方、[[19世紀]]には、{{math|1}} は素数であると考える数学者が多く存在した。例えば、[[デリック・ノーマン・レーマー|レーマー]]の {{math|10,006,721}} までの素数表（後の[[1956年]]に再版<ref>{{Harvnb|Riesel|1994|p=36}}</ref>）では、素数は {{math|1}} から始まるものとして書かれている<ref>{{Harvnb|Conway|Guy|1996|pp=129f}}</ref>。[[アンリ・ルベーグ]]は、{{math|1}} を素数だと考えた最後の専門的な数学者だと言われている<ref>{{Harvnb|Derbyshire|2003|p=33}}</ref>。 {{math|1}} は素数であると仮定しても、素因数分解の可能性は成り立ち、数学の大部分の命題ではそのままの文面で変わらず有効であるが、素因数分解の一意性は成り立たなくなる。{{math|1}} が素数だとすると、例えば {{math|6}} の素因数分解は、（積の順序を除いても） :{{math|6 {{=}} 2 × 3 {{=}} 1 × 2 × 3 {{=}} 1{{sup|2}} × 2 × 3 {{=}} …}} と無数の素因数分解を与えることになり、一意性が成り立たなくなる。さらに、{{math|1}} 以外の素数で成り立つ様々な性質がある（例えば、自然数とそれに対応する[[オイラーのφ関数]]や[[約数関数]]の値との関係など）<ref>[http://primefan.tripod.com/Prime1ProCon.html "Arguments for and against the primality of 1"].</ref><ref>[http://primes.utm.edu/notes/faq/one.html "Why is the number one not prime?"]</ref>。 == 歴史 == {{節スタブ}} {{main|素数の歴史}} [[紀元前16世紀|紀元前1600年]]頃の[[エジプト第2中間期]]において、素数に関する知識が部分的に知られていたことが、[[リンド数学パピルス]]などの資料によって示唆されている。例えば分数を[[エジプト式分数]]で表す場合、素数と合成数の場合で異なる計算をしなければならないからである。しかし、記録に残っている限りにおいて、明確に素数を研究対象としたのは[[古代ギリシア]]人が最初である。紀元前約300年頃に書かれた[[エウクレイデス|ユークリッド]]の『[[ユークリッド原論|原論]]』には[[素数が無数に存在することの証明|素数が無数に存在すること]]や、その他の素数の性質が証明されている。また、ユークリッドは[[メルセンヌ数|メルセンヌ素数]]から[[完全数]]を構成する方法を示している。ギリシアの数学者、[[エウクレイデス|エラトステネス]]に因んで名付けられた'''[[エラトステネスの篩|エラトステネスの篩（ふるい）]]'''は、素数を列挙するための計算方法である。 古代ギリシア時代の後、[[17世紀]]になるまで素数の研究にはそれほどの進展が無かった。[[1640年]]に、[[ピエール・ド・フェルマー]]はフェルマーの小定理を（未証明ではあるが）述べた。この定理は後に[[ゴットフリート・ライプニッツ|ライプニッツ]]と[[レオンハルト・オイラー|オイラー]]によって証明された。 == 素数の個数 == {{Main|素数が無数に存在することの証明}} [[画像:Ulam 1.png|thumb|自然数を渦巻状に並べていき、素数だけを黒く塗ったもの（[[ウラムの螺旋]]）。<br>素数が高密度に集まった対角線、水平線、垂線が見て取れる。素数の分布が極めて難解であるために、この素数のパターンが示す事実については未だに明らかにされていない。]] 素数が無数に存在することは既に[[古代ギリシア]]時代から知られていて、[[エウクレイデス|ユークリッド]]が彼の著作『[[ユークリッド原論|原論]]』<ref name="euclid">{{Harvnb|ユークリッド|2011|loc=9-20}}</ref>の中で証明している。 === ユークリッドによる証明 === ;『原論』第9巻 命題20<ref name="euclid" /> :素数の個数はいかなる定められた素数の個数よりも多い。 :定められた個数の素数を {{math|''p''{{sub|1}}}}, {{math|''p''{{sub|2}}}}, …, {{mvar|p{{sub|n}}}} とせよ。{{math|''p''{{sub|1}}}}, {{math|''p''{{sub|2}}}}, …, {{mvar|p{{sub|n}}}} より多い個数の素数があると主張する。 ;『原論』による証明{{refnest|group=注釈|ユークリッドによる証明では、変数・数式・任意の個数を示すパラメーター {{mvar|n}} を使用せずに、定められた個数が 3 個の素数 {{mvar|Α}}, {{mvar|Β}}, {{mvar|Γ}} の場合に証明している。これを「準一般的」な証明という。詳細は[[素数が無数に存在することの証明#ユークリッド]]を参照。}} :定められた素数の個数が {{mvar|n}} 個であるとき、{{mvar|n}} 個の素数を小さい順番にならべて {{mvar|i}} 番目の素数を {{mvar|p{{sub|i}}}} とする。 :{{math|1 < ''p''{{sub|1}} < ''p''{{sub|2}} < … < ''p{{sub|n}}''.}} :このとき、{{mvar|n}} 個の素数をすべて掛け合わせた数に {{math|1}} を加えた数を {{mvar|q}} とすると、 :{{math|''q'' {{=}} ''p''{{sub|1}} × ''p''{{sub|2}} × … × ''p{{sub|n}}'' + 1}}. :{{mvar|q}} は有限個の自然数の積に {{math|1}} を加えた数なので {{math|1}} より大きい自然数である。ゆえに、{{mvar|q}} は素数または合成数のどちらかである。 :{{mvar|q}} が素数のとき、{{mvar|q}} は最大の素数 {{mvar|p{{sub|n}}}} より大きい素数になるので、定められた個数の素数よりも多くの素数が存在する。 :{{mvar|q}} が合成数のとき、{{mvar|q}} を割り切る素数が存在する。いっぽう、{{mvar|q}} の定義より、すべての {{mvar|p{{sub|i}}}} で割った余りは {{math|1}} になるので、{{mvar|q}} はすべての {{mvar|p{{sub|i}}}} で割り切れない。したがって、すべての {{mvar|p{{sub|i}}}} 以外に素数が存在する。すなわち、定められた個数の素数よりも多くの素数が存在する。（[[Q.E.D.|証明終]]） ;例 :自然数の有限集合 {{mvar|A}} の全ての要素を掛け合わせた自然数を {{math|''f''(''A'')}} とする。 :定められた個数の素数から成る集合を {{math|''A''{{sub|3}} {{=}} {2, 3, 5} }} とするとき、{{math|''f''(''A''{{sub|3}}) {{=}} 2 × 3 × 5 + 1 {{=}} 31}} は素数なので、新しい素数 {{math|31}} が得られる。したがって、定められた個数より多くの素数が存在する。 :定められた個数の素数から成る集合を {{math|''A''{{sub|4}} {{=}} {2, 3, 5, 31} }} とするとき、{{math|''f''(''A''{{sub|4}}) {{=}} 2 × 3 × 5 × 31 + 1 {{=}} 931 {{=}} 7 × 7 × 19}} なので、新しい素数 {{math|7}} と {{math|19}} が得られる。したがって、定められた個数より多くの素数が存在する。 === 他の証明 === 上記のユークリッドによる証明以外にも、素数が無数に存在することの証明方法が存在する。 *素数の逆数の和が発散することを利用した証明{{refnest|group=注釈|[[レオンハルト・オイラー]]による。現代的な用語で言えば、[[リーマンゼータ関数]]のオイラー積表示を用いる<ref name="Ribenboim">{{Harvnb|Ribenboim|2001|loc=第1章}}</ref>。}}（''[[#素数の逆数和]]を参照''） *2つの異なる[[フェルマー数]]が互いに素であることを利用した証明{{refnest|group=注釈|[[ジョージ・ポーヤ]]による<ref name="Ribenboim" /><ref name="Aigner&Ziegler">{{Harvnb|アイグナー|ツィーグラー|2012|loc=第1章}}</ref>。}} *整数の集合に、[[等差数列]]の族を開基とする[[位相空間|位相]]を入れる証明{{refnest|group=注釈|[[ヒレル・ファステンバーグ]]による。[[:en:Furstenberg's proof of the infinitude of primes]]を参照。<!-- 日本語の文献では共立「素数大百科」にあるそうですが未確認なのでコメントアウトしておきます。どなたか確認されたら追加してください。 -->}} *{{math|''n'' ≥ 2}} に対して、{{math|''n''(''n'' + 1)}} は少なくとも相異なる2個の素因数を持つことを利用した証明{{refnest|group=注釈|[[素数が無数に存在することの証明#サイダック]]を参照<ref>{{doi|10.2307/27642094}} http://primes.utm.edu/notes/proofs/infinite/Saidak.html</ref>。}}。おそらく最も短い証明。 == 素数判定と素因数分解 == {{main|素数判定|素因数分解}} 与えられた自然数 {{mvar|n}} が素数であるか合成数であるかを判定するための[[アルゴリズム]]が多数考案されている。最も素朴な方法は、{{math|2}} から {{math|{{sqrt|''n''}}}} 以下の素数まで順番に割っていく、'''試し割り'''と呼ばれる方法である。{{mvar|n}} が {{math|{{sqrt|''n''}}}} 以下の全ての素数で割り切れなければ {{mvar|n}} は素数である。試し割りは、{{mvar|n}} が大きくなるに従って、急速に速度が低下するため、実用的ではない。任意の数に適用できる試し割りよりも高速なアルゴリズムが考案されている。また、特殊な形をした数に対してはより高速なアルゴリズムも存在する。素数判定は、与えられた数が素数であるか否かだけを判定するものであるが、素因数分解とはより強く、与えられた数の全ての素因数を列挙することであるとも言える。 == 分布 == ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。素数のない、いくらでも長い区間が存在する。例えば、{{math|''n'' ≥ 2}} に対して、連続する {{math|''n'' &minus; 1}} 個の自然数 {{math|''n''[[階乗|!]] + 2, …, ''n''! + ''n''}} はそれぞれ、より小さい {{math|2, …, ''n''}} で割り切れるので、どれも素数でない。また、比較的小さな数では、{{math|[[114]]}} から {{math|[[126]]}} まで{{math|13}}個連続で合成数である。（この区間の最初の値は{{OEIS|A008950}}を、終了の値は{{OEIS|A008995}}をその区間幅については{{OEIS|A008996}}を参照） これに関して、次の'''[[素数定理]]'''は有名である。この定理は[[1896年]]に、[[ジャック・アダマール|アダマール]]とド・ラ・ヴァレ・プサンによって独立に証明された。 {{mvar|x}} 以下の素数の個数を {{math|{{π}}(''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年]]に[[アトル・セルバーグ]]と[[ポール・エルデシュ]]は独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。 次のような定理もある。 :「任意の自然数 {{mvar|n}} に対して、{{math|''n'' < ''p'' ≤ 2''n''}} を満たす素数 {{mvar|p}} が存在する」（'''[[ベルトランの仮説]]'''、[[パフヌティ・チェビシェフ|チェビシェフ]]の定理） この主張は「任意の素数 {{mvar|p}} の次の素数は {{math|2''p''}} 未満」とも言い換えられる。したがって、2017年5月現在知られている最大の素数 {{math|2{{sup|74207281}} &minus; 1}} の次の素数は {{math|2{{sup|74207282}} &minus; 2}} 未満である。 しかしながら、例えば {{math|''n''{{sup|2}}}} と {{math|(''n'' + 1){{sup|2}}}} の間に素数が存在するかという問題は未解決である（[[ルジャンドル予想]]）。 === 素数計数 === [[2015年]]に、[[ゴールドバッハの予想]]検証プロジェクトは {{math|4 × 10{{sup|18}}}} 以下の全ての素数（9京5676兆2609億388万7607個、約 10{{sup|17}}個）を計算したと報告した<ref>Tomás Oliveira e Silva, [http://www.ieeta.pt/~tos/goldbach.html Goldbach conjecture verification]. Retrieved 16 July 2013.</ref><ref>{{OEIS|id=A080127}}</ref>が、結果は保存されていない。しかしながら、[[素数計数関数]]を計算するには、実際に素数を数えるより高速な公式が存在する。この公式を使って、{{math|10{{sup|23}}}} 以下に 19垓2532京391兆6068億396万8923個（約 2{{e|21}}個）の素数があると計算された。 また、別の計算によると、[[リーマン予想]]が真であると仮定した場合、{{math|10{{sup|24}}}} 以下に 184垓3559京9767兆3492億86万7866個（約 2{{e|22}}個) の素数が存在する<ref name="Franke">{{Cite web |title = Conditional Calculation of pi(10{{sup|24}}) |url = http://primes.utm.edu/notes/pi(10%5E24).html |author = Jens Franke |date = 2010-7-29 |accessdate = 2015-02-02 }}</ref>。 === 分布の視覚化 === *[[エラトステネスの篩]] *[[ウラムの螺旋]] *プリヒタの素数円 == 素数に関連する主な性質 == === 素数の逆数和 === 素数の[[逆数]]の和は（[[無限大]]に）[[発散級数|発散]]する。この命題は『素数は無数に存在する』という命題を含んでいる（有限個ならば[[収束]]、すなわち発散しないはずである）が、それだけではなく素数の分布に関してより多くの情報を提供している。 この結果は最初に[[レオンハルト・オイラー]]により[[リーマンゼータ関数|ゼータ関数]]を研究することでもたらされた。以下の証明は[[ポール・エルデシュ]]による、より直接的で、また簡潔な証明である{{refnest|group=注釈|『天書の証明』第1章<ref name="Aigner&Ziegler" />を参照。原論文は {{Citation|last=Erdös|first=P.|author-link=ポール・エルデシュ|date=1938-07|title=Über die Reihe ∑ 1/p|journal=Mathematica, Zutphen B|publisher=|language=German|pages=1-2|url=http://www.renyi.hu/~p_erdos/1938-12.pdf|format=PDF}}。}}。素数が無数に存在することを証明に用いないため、その証明をも含んでいる。 ;エルデシュによる証明 素数の逆数和は収束すると仮定する。{{mvar|i}} 番目の素数を {{mvar|p{{sub|i}}}} で表すと、 :<math>\sum_{i=N+1}^\infty \frac{1}{p_i} <\frac{1}{2} \cdots (1)</math> を満たす {{mvar|N}} が存在する。 {{mvar|n}} 以下の自然数のうち最大素因数が {{mvar|p{{sub|N}}}} 以下のものからなる集合を {{mvar|A{{sub|n}}}} とする。任意の {{math|''k'' ∈ ''A{{sub|n}}''}} に対して、 :{{math|''k'' {{=}} ''u''{{sup|2}}''v''}}（{{mvar|v}} の各素因数の指数は全て {{math|1}}） と表示すると、{{mvar|v}} は高々 {{math|2{{sup|''N''}}}} 通り、{{math|''u''{{sup|2}} ≤ ''k'' ≤ ''n''}} より :{{math|#''A{{sub|n}}'' ≤ 2{{sup|''N''}}{{sqrt|''n''}}}} …(2) {{mvar|A{{sub|n}}{{sup|c}}}} の元は、{{math|''p''{{sub|''N''+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} <\frac{n}{2}</math> {{math|#''A{{sub|n}}{{sup|c}}'' {{=}} ''n'' &minus; #''A{{sub|n}}''}} より :{{math|{{sfrac|''n''|2}} < #''A{{sub|n}}''}} …(3) (2), (3) より {{math|{{sfrac|''n''|2}} < 2{{sup|''N''}} {{sqrt|''n''}}}}, ∴ {{math|''n'' < 2{{sup|2''N''+2}}}}。これは {{mvar|n}} の任意性に矛盾。（[[Q.E.D.|証明終]]） [[双子素数]]に限ると、逆数和は {{math|''B''{{sub|2}} {{=}} 1.902…}} に収束することが証明されている（[[ブルン定数]]）。 === その他の性質 === *{{math|(''a'', ''m'') {{=}} 1}} のとき、[[等差数列]]：{{math2|''a'', ''a'' + ''m'', ''a'' + 2''m'', …}} には素数の項が無数に含まれている。（[[ディリクレの算術級数定理]]） *素数 {{mvar|p}} に対して、{{math|(''a'', ''p'') {{=}} 1 ⇒ ''a''{{sup|''p''&minus;1}} ≡ 1 (mod ''p'')}}（[[フェルマーの小定理]]） *{{mvar|p}} が素数 {{math|⇔ (''p'' &minus; 1)! ≡ &minus;1 (mod ''p'')}}（[[ウィルソンの定理]]） *素数の2乗差は {{math|5}} の倍数, {{math|3}} の倍数, {{math|8}} の倍数のいずれかである。 :{{math|5 ( {{=}} 3{{sup|2}} &minus; 2{{sup|2}}), 16 ( {{=}} 5{{sup|2}} &minus; 3{{sup|2}}), 21 ( {{=}} 5{{sup|2}} &minus; 2{{sup|2}}), 24 ( {{=}} 7{{sup|2}} &minus; 5{{sup|2}}), 40 ( {{=}} 7{{sup|2}} &minus; 3{{sup|2}}), …}} == 素数生成式 == [[レオンハルト・オイラー|オイラー]]の発見した式、{{math|''f''(''n'') {{=}} ''n''{{sup|2}} + ''n'' + 41}} は、{{math|''n'' {{=}} 0, …, 39}} で全て素数となる。これは、虚[[二次体]] <math>\mathbb{Q}(\sqrt{-163})</math> の[[類数]]が {{math|1}} であることと関係している<ref>{{Harvnb|Ribenboim|2001|loc=第3章}}</ref><ref>{{OEIS|A005486}}</ref><ref>{{OEIS|A202018}}</ref>。 *{{math|''f''(''n'') {{=}} ''n''{{sup|2}} + ''n'' + ''p''}} が {{math|0 ≤ ''n'' ≤ ''p'' &minus; 2}} で素数を取るような素数 {{mvar|p}} の値を「オイラーの幸運数」という。{{math|''p'' {{=}} [[2]], [[3]], [[5]], [[11]], [[17]], [[41]]}}（{{OEIS|A014556}}） 多変数の高次多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、{{math|''k'' + 2}} が素数となる必要十分条件は、次の[[ディオファントス方程式]]が自然数解を持つことである<ref>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}}</ref>: :{{math|''wz + h + j &minus; q'' {{=}} 0}} :{{math|(''gk'' + 2''g'' + ''k'' + 1)(''h'' + ''j'') + ''h'' &minus; ''z'' {{=}} 0}} :{{math|(16''k'' + 1){{sup|3}}(''k'' + 2)(''n'' + 1){{sup|2}} + 1 &minus; ''f''{{sup|2}} {{=}} 0}} :{{math|2''n'' + ''p'' + ''q'' + ''z'' &minus; ''e'' {{=}} 0}} :{{math|''e''{{sup|3}}(''e'' + 2)(''a'' + 1){{sup|2}} + 1 &minus; ''o''{{sup|2}} {{=}} 0}} :{{math|(''a''{{sup|2}} &minus; 1)''y''{{sup|2}} + 1 &minus; ''x''{{sup|2}} {{=}} 0}} :{{math|16''r''{{sup|2}}''y''{{sup|4}}(''a''{{sup|2}} &minus; 1) + 1 &minus; ''u''{{sup|2}} {{=}} 0}} :{{math|''n'' + ''l'' + ''v'' &minus; ''y'' {{=}} 0}} :{{math|(''a''{{sup|2}} &minus; 1)''l''{{sup|2}} + 1 &minus; ''m''{{sup|2}} {{=}} 0}} :{{math|''ai'' + ''k'' + 1 &minus; ''l'' &minus; ''i'' {{=}} 0}} :{{math|[{''a'' + ''u''{{sup|2}}(''u''{{sup|2}} &minus; ''a'')}{{sup|2}} &minus; 1](''n'' + 4''dy''){{sup|2}} + 1 &minus; (''x'' + ''cu''){{sup|2}} {{=}} 0}} :{{math|''p'' + ''l''(''a'' &minus; ''n'' &minus; 1) + ''b''(2''an'' + 2''a'' &minus; ''n''{{sup|2}} &minus; 2''n'' &minus; 2) &minus; ''m'' {{=}} 0}} :{{math|''q'' + ''y''(''a'' &minus; ''p'' &minus; 1) + ''s''(2''ap'' + 2''a'' &minus; ''p''{{sup|2}} &minus; 2''p'' &minus; 2) &minus; ''x'' {{=}} 0}} :{{math|''z'' + ''pl''(''a'' &minus; ''p'') + ''t''(2''ap'' &minus; ''p''{{sup|2}} &minus; 1) &minus; ''pm'' {{=}} 0}} 誤解されやすいが、素数が無数に存在することの、[[#ユークリッドによる証明]]で使われる手順からは、必ずしも素数を得ることができない。なぜなら最初の仮定「最大の素数 {{mvar|p{{sub|n}}}} が存在する」が正しくないからである。実際に、{{math|''n'' {{=}} 6}} で :{{math|2 × 3 × 5 × 7 × 11 × 13 + 1 {{=}} 30031 {{=}} 59 × 509}} と、自明でない約数に分解できてしまう（最小の反例）。 == 特殊な形をした素数 == *[[メルセンヌ数#メルセンヌ素数|メルセンヌ素数]]：{{math|2{{sup|''n''}} &minus; 1}}（{{mvar|n}} は素数が必要、{{math|''n'' {{=}} 2, 3, 5, 7, 13, …}}） *[[フェルマー数#フェルマー素数|フェルマー素数]]：{{math|2{{sup|2{{sup|''n''}}}} + 1}} *オイラー素数：{{math|''n''{{sup|2}} + ''n'' + 41}} *[[階乗素数]] **{{math|''n''! + 1}}型 {{math|(''n'' {{=}} 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, …)}} **{{math|''n''! &minus; 1}}型 {{math|(''n'' {{=}} 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, …)}} *[[素数階乗素数]]：{{math|''p''# ± 1}}（{{mvar|p}} は素数、{{math|''p''#}} は {{mvar|p}} の[[素数階乗]]） *[[レピュニット]] {{math|''R''{{sub|2}}, ''R''{{sub|19}}, ''R''{{sub|23}}, …}}（{{mvar|R{{sub|n}}}} は {{math|1}} が {{mvar|n}} 個続く数、通常は[[位取り記数法|基数]]を {{math|10}} にとる） *[[双子素数]]（差が {{math|2}} である2つの素数） *[[いとこ素数]]（差が {{math|4}} である2つの素数） *[[セクシー素数]]（差が {{math|6}} である2つの素数） *[[三つ子素数]]（3つの素数の組 {{math|(''p'', ''p'' + 2, ''p'' + 6)}} または {{math|(''p'', ''p'' + 4, ''p'' + 6)}}（{{math|(''p'', ''p'' + 2, ''p'' + 4}})型は {{math|([[3]], [[5]], [[7]])}} のみ。） *[[四つ子素数]]（{{math|''p'', ''p'' + 2, ''p'' + 6, ''p'' + 8}} が全て素数） *[[ソフィー・ジェルマン素数]]（{{mvar|p}} と {{math|2''p'' + 1}} がともに素数） *[[安全素数]]（{{mvar|p}} と {{math|(''p'' &minus; 1) / 2}} がともに素数） *[[スーパー素数]]（素数列における素数番目の素数） *[[切り捨て可能素数]]（与えられた基数において {{math|0}} を含まず、左右から数を取っていった数がすべて素数である素数） *[[陳素数]]（{{math|''p'' + 2}} が[[半素数]]またはともに素数） *[[正則素数]]（[[円分体|円の {{mvar|p}} 分体]]の[[代数体#類数|類数]]を割り切らない奇素数） *[[正則素数|非正則素数]]（円の {{mvar|p}} 分体の類数を割り切る奇素数） *[[フィボナッチ素数]]（[[フィボナッチ数]]の数列に含まれる素数） *その他の素数 **{{math|''n''{{sup|2}} + 1}} の形で表せる素数：{{math|[[2]], [[5]], [[17]], [[37]], [[101]], [[197]], [[257]], [[401]], [[577]], [[677]], 1297, …}}（{{OEIS|A002496}}） **{{math|''n''{{sup|4}} + 1}} の形で表せる素数：{{math|[[2]], [[17]], [[257]], 1297, 65537, 160001, …}}（{{OEIS|A037896}}） **{{math|''n''{{sup|4}} + (''n'' + 1){{sup|4}}}} の形で表せる素数：{{math|[[17]], [[97]], [[337]], [[881]], 3697, …}}（{{OEIS|A152913}}） == 未解決問題 == *[[双子素数]]の予想：双子素数は無数に存在する、という予想。 *[[ゴールドバッハの予想]]：{{math|6}} 以上の全ての偶数は 2 つの奇素数の和で表すことができる、という予想。 *[[弱いゴールドバッハ予想]]：{{math|7}} 以上の全ての奇数は 3 つの素数の和で表すことができる、という予想。ただし[[ハラルド・ヘルフゴット]]による証明が[[2013年]]に発表されている<ref>{{cite arXiv |eprint = 1305.2897 |title = Major arcs for Goldbach's theorem |last = Helfgott |first = H.A. |class = math.NT |year = 2013 }}</ref><ref>{{cite arXiv |eprint = 1205.5252/ |title = Minor arcs for Goldbach's problem |last = Helfgott |first = H.A. |class = math.NT |year = 2012 }}</ref><ref name="humboldt-professur.de">http://www.humboldt-professur.de/en/preistraeger/preistraeger-2015/harald-andres-helfgott</ref>。 *[[ルジャンドル予想]]：全ての {{mvar|n}} に対し、{{math|''n''{{sup|2}}}} と {{math|(''n'' + 1){{sup|2}}}} の間に素数が存在するかという予想。 *既知の[[フェルマー数#フェルマー素数|フェルマー素数]]以外に、フェルマー数にフェルマー素数は存在するか？ *[[メルセンヌ数|メルセンヌ素数]]は無数に存在するか？ *[[ソフィー・ジェルマン素数]]、[[安全素数]]は無数に存在するか？ *[[フィボナッチ数|フィボナッチ数列]]には、素数である項が無数に現れるか？（[[フィボナッチ素数]]） *[[幸運数]]でも素数でもあるような数は無数に存在するか？ *[[ハッピー数|ハッピー素数]]は無数に存在するか？ *{{math|''n''{{sup|2}} + 1}} の形の素数は無数に存在するか？（[[ブニャコフスキー予想]]） == 応用 == 長い間、[[数論]]、その中でもとりわけ素数に関する研究は、その分野以外での応用の全くない純粋数学の見本と見なされていた。特に、イギリスの数論研究者である[[ゴッドフレイ・ハロルド・ハーディ|ハーディ]]は、自身の研究が軍事的に何の重要性も持たないことを誇っていた。しかし、この見方は1970年代には覆されてしまった。素数が公開鍵暗号のアルゴリズムに使用できると広く知られるようになったためである。現在では素数は[[ハッシュテーブル]]や[[擬似乱数]]生成にも用いられ、工学的応用上重要度の高いものとなっている。 === 公開鍵暗号 === {{main|公開鍵暗号}} 公開鍵暗号のアルゴリズムとして、[[RSA暗号]]や[[ディフィー・ヘルマン鍵共有]]といった、大きな数の[[素因数分解]]は困難であるという性質に基礎を置くものがある。RSA暗号は、2つの（大きな）素数の掛け算は比較的簡単に（効率的に）行えるが、その積を素因数分解して元の2つの素数を求めることは難しいという事実に基づいている。 === 自然界の素数 === 自然界に現れる素数の一例として、[[素数ゼミ]]と呼ばれる[[セミ]]の一種がいる。[[アメリカ合衆国]]に分布するこのセミの成虫は、ある周期ごとに、13年ないしは17年間の周期で大量発生する。成虫になった後は、数週間だけを地上で成虫として過ごし交配と産卵を行う。このセミが素数周期で発生する理由として、寄生虫や捕食者に対抗するための進化であるという説や近縁種との交雑を避けるためであるという説がある。つまり、もしこのセミが12年の発生周期を持っていた場合、12の約数である2, 3, 4, 6年の寿命を持つ捕食者と同時に発生してしまうことになり、捕食対象にされやすくなる。また、地理的に近い場所で12年周期と15年周期のセミが存在した場合、60年ごとに2種は同時に発生し、交雑してしまう可能性がある。すると、雑種は発生周期がズレてしまい、同種のセミとの交尾の機会が失われる。素数の周期を持つものは交雑が起こりにくく、淘汰されにくいと考えられる<ref>{{Harvnb|吉村|2008}}</ref>。 また、[[リーマンゼータ関数|ゼータ関数]]上の零点の分布の数式が、原子核のエネルギー間隔を表す式と一致することを示し、素数と核物理現象との関連性が示唆されている。 {{main|リーマン予想}} == 連続素数 == === 連続素数和 === {|class="wikitable" !連続数!!数!!参照!!含まれる素数列 |- |{{center|2}}||{{math|'''[[5]]''', [[8]], [[12]], [[18]], [[24]], [[30]], [[36]], [[42]], [[52]], [[60]], [[68]], [[78]], [[84]], …}}||{{OEIS|A001043}}|| |- |{{center|3}}||{{math|[[10]], [[15]], '''[[23]]''', '''[[31]]''', '''[[41]]''', [[49]], '''[[59]]''', '''[[71]]''', '''[[83]]''', '''[[97]]''', '''[[109]]''', …}}||{{OEIS|A034961}}||{{OEIS|A034962}} |- |{{center|4}}||{{math|'''[[17]]''', [[26]], [[36]], [[48]], [[60]], [[72]], [[88]], [[102]], [[120]], [[138]], [[152]], …}}||{{OEIS|A034963}}|| |- |{{center|5}}||{{math|[[28]], [[39]], '''[[53]]''', '''[[67]]''', '''[[83]]''', '''[[101]]''', [[119]], '''[[139]]''', [[161]], '''[[181]]''', …}}||{{OEIS|A034964}}||{{OEIS|A034965}} |- |{{center|6}}||{{math|'''[[41]]''', [[56]], [[72]], [[90]], [[112]], [[132]], [[156]], [[180]], [[204]], [[228]], …}}||{{OEIS|A127333}}|| |- |{{center|7}}||{{math|[[58]], [[75]], [[95]], [[119]], [[143]], [[169]], '''[[197]]''', '''[[223]]''', '''[[251]]''', '''[[281]]''', …}}||{{OEIS|A127334}}|| {{OEIS|A082246}} |- |{{center|8}}||{{math|[[77]], [[98]], [[124]], [[150]], [[180]], [[210]], [[240]], [[270]], [[304]], …}}||{{OEIS|A127335}}|| |- |{{center|9}}||{{math|[[100]], '''[[127]]''', [[155]], [[187]], [[221]], [[253]], [[287]], [[323]], [[363]], …}}||{{OEIS|A127336}}||{{OEIS|A082251}} |- |{{center|10}}||{{math|[[129]], [[158]], [[192]], [[228]], [[264]], [[300]], [[340]], [[382]], [[424]], …}}||{{OEIS|A127337}}|| |- |{{center|11}}||{{math|[[160]], [[195]], '''[[233]]''', '''[[271]]''', '''[[311]]''', '''[[353]]''', [[399]], '''[[443]]''', '''[[491]]''', …}}||{{OEIS|A127338}}||{{OEIS|A127340}} |- |{{center|12}}||{{math|'''[[197]]''', [[236]], [[276]], [[318]], [[364]], [[412]], [[460]], [[510]], [[562]], …}}||{{OEIS|A127339}}|| |- |{{center|13}}||{{math|[[238]], [[279]], [[323]], [[371]], [[423]], [[473]], [[527]], …}}|| ||{{OEIS|A127341}} |} {{main2|各連続素数和の最初の数|{{OEIS|A007504}}|この数が素数になる数|{{OEIS|A013918}}}} === 連続素数積 === {|class="wikitable" !連続数!!数!!参照 |- |{{center|2}}||{{math|[[6]], [[15]], [[35]], [[77]], [[143]], [[221]], [[323]], [[437]], [[667]], [[899]], 1147, 1517, 1763, …}}||{{OEIS|A006094}} |- |{{center|3}}||{{math|[[30]], [[105]], [[385]], [[1001]], 2431, 4199, 7429, 12673, 20677, 33263, 47027, …}}||{{OEIS|A046301}} |- |{{center|4}}||{{math|[[210]], 1155, 5005, 17017, 46189, 96577, 215441, 392863, 765049, …}}||{{OEIS|A046302}} |- |{{center|5}}||{{math|[[2310]], 15015, 85085, 323323, 1062347, 2800733, …}}||{{OEIS|A046303}} |- |{{center|6}}||{{math|30030, 255255, 1616615, 7436429, 30808063, 86822723, …}}||{{OEIS|A046324}} |- |{{center|7}}||{{math|510510, 4849845, …}}||{{OEIS|A046325}} |- |{{center|8}}||{{math|9699690, 111546435, …}}||{{OEIS|A046326}} |- |{{center|9}}||{{math|223092870, 3234846615, …}}||{{OEIS|A046327}} |- |{{center|10}}||{{math|6469693230, 100280245065, …}}||{{OEIS|A127342}} |- |{{center|11}}||{{math|200560490130, 3710369067405, …}}||{{OEIS|A127343}} |- |{{center|12}}||{{math|7420738134810, 152125131763605, …}}||{{OEIS|A127344}} |} {{main2|各連続素数積の最初の数|素数階乗}} == 脚注 == {{脚注ヘルプ}} === 注釈 === {{Reflist|group="注釈"}} === 出典 === {{Reflist|2}} == 参考文献 == *{{Citation|last1=Aigner|first1=Martin|last2=Ziegler|first2=Günter M.|year=2010|title=Proofs from THE BOOK|publisher=Springer-Verlag|edition=4th|isbn=978-3-642-00856-6|url=http://www.springer.com/jp/book/9783642008566}} **{{Cite book|和書|author=M・アイグナー|coauthors=G・M・ツィーグラー|others=[[蟹江幸博]] 訳|date=2012-09-01|title=天書の証明|edition=縮刷版|publisher=丸善出版|isbn=978-4-621-06535-8|url=https://pub.maruzen.co.jp/book_magazine/book_data/search/9784621065358.html|ref={{Harvid|アイグナー|ツィーグラー|2012}}}} *{{Citation|last1=Conway|first1=John Horton|author1-link=John Horton Conway|last2=Guy|first2=Richard K.|author2-link=Richard K. Guy|title=The Book of Numbers|publisher=Copernicus|location=New York|isbn=978-0-387-97993-9|year=1996}} **{{Cite book|和書|author=[[ジョン・ホートン・コンウェイ|J・H・コンウェイ]]|coauthors=[[R・K・ガイ]]|others=[[根上生也]] 訳|date=2012-01|title=数の本|publisher=[[丸善出版]]|isbn=978-4-621-06207-4|url=https://pub.maruzen.co.jp/book_magazine/book_data/search/9784621062074.html|ref={{Harvid|コンウェイ|ガイ|2012}}}} *{{Cite book|和書|author=真実のみを記述する会|date=2011-08|title=素数表150000個|publisher=[[暗黒通信団]]|isbn=978-4-87310-156-9|url=http://ankokudan.org/d.htm?detail156-detailread-j.html|ref={{Harvid|真実のみを記述する会|2011}}}} *{{Cite book|和書|author= Manfred Robert Schroeder|translator=[[平野浩太郎]]・[[野村孝徳]] 共|date=1995-02-01|title=科学と通信における数論　暗号，物理学，ディジタル情報，計算法，自己相似性を含む|volume=〈上〉|publisher=[[パスカル研究会]]（出版）[[コロナ社]]（発売）|isbn=978-4-339-08216-6|url=https://www.coronasha.co.jp/np/isbn/9784339082166/|pages=33-68}} *{{Citation|last1=Derbyshire|first1=John|title=Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics|year=2003|publisher=Joseph Henry Press|location=Washington, D.C.|isbn=978-0-309-08549-6|oclc=249210614}} **{{Cite book|和書|author=ジョン・ダービーシャー|others=[[松浦俊輔]] 訳|date=2004-08-30|title=素数に憑かれた人たち　リーマン予想への挑戦|publisher=[[日経BP社]]（出版）[[日経BP出版センター]]（発売）|isbn=978-4-8222-8204-2|url=http://store.nikkeibp.co.jp/item/books/P82040.html|ref={{Harvid|ダービーシャー|松浦}}}} *{{Cite book|和書|author=[[本橋洋一]]|origdate=2009-11-01|date=2012|title = 解析的整数論|edition=第2刷|volume =〈1〉素数分布論|series=朝倉数学大系|publisher=[[朝倉書店]]|isbn=978-4-254-11821-6|url=https://www.asakura.co.jp/books/isbn/978-4-254-11821-6/}} - 第2刷 2012：加筆含む。 *{{Cite web|author=本橋洋一|date=2005-03-26|url=http://mathsoc.jp/publication/tushin/1001/motohashi.pdf|format=PDF|title=素数の翼に乗って|publisher=日本数学会年会市民講演|accessdate=2016-12-29|ref={{Harvid|本橋|2005}}}} *{{Cite book|和書|author=[[エウクレイデス|ユークリッド]]|translator=[[中村幸四郎]]・[[寺阪英孝]]・[[伊東俊太郎]]・[[池田美恵]]|date=2011-5-25|title=ユークリッド原論|edition=追補版|publisher=[[共立出版]]|isbn=978-4-320-01965-2|url=http://www.kyoritsu-pub.co.jp/bookdetail/9784320019652|ref={{Harvid|ユークリッド|2011}}}} *{{Cite book|和書|author=[[吉村仁]]|date=2008-07-16|title=17年と13年だけ大発生? 素数ゼミの秘密に迫る!|series=サイエンス・アイ新書 072|publisher=[[ソフトバンククリエイティブ]]|isbn=978-4-7973-4258-1|url=http://www.sbcr.jp/products/4797342581.html|ref={{Harvid|吉村|2008}}}} *{{Citation|last1=Riesel|first1=Hans|title=Prime numbers and computer methods for factorization|publisher=Birkhäuser|location=Basel, Switzerland|isbn=978-0-8176-3743-9|year=1994}} *{{Citation|last=Ribenboim|first=Paulo|year=2004|title=The Little Book of Bigger Primes|publisher=Springer-Verlag|edition=2nd|isbn=978-0-387-20169-6|url=http://www.springer.com/jp/book/9780387201696}} **{{Cite book|和書|author=Paulo Ribenboim|translator=[[吾郷孝視]]|date=2001-10-20|title=素数の世界　その探索と発見|edition=第2版|publisher=[[共立出版]]|isbn=978-4-320-01684-2|url=http://www.kyoritsu-pub.co.jp/bookdetail/9784320016842|ref={{Harvid|Ribenboim|2001}}}} == 関連項目 == {{commonscat|Prime numbers}} {{Div col}} *[[違法素数]] *[[エマープ]] *[[エラトステネスの篩]] *[[巨大な素数の一覧]] *[[コープランド-エルデシュ定数]] *[[素数の一覧]] *[[ピタゴラス素数]] *[[プライム (小惑星)]] - [[小惑星番号]]7919が1000番目の素数であることに因む小惑星。 {{Div col end}} *[[Regimbalの素数公式]] == 外部リンク == * [http://primes.utm.edu/ The Prime Page] * {{MathWorld|title=Prime Number|urlname=PrimeNumber}} * {{nlab|title=prime number|urlname=prime+number}} * {{PlanetMath|title=prime|urlname=Prime}} * {{SpringerEOM|title=Prime number|urlname=Prime_number}} {{素数の分類}} {{Normdaten}} {{DEFAULTSORT:そすう}} [[Category:初等数学]] [[Category:数論]] [[Category:整数の類]] [[Category:素数|*]] [[Category:数学に関する記事]]

素数 に戻る。