素数
出典: Wikipedio
|
プライバシー・ポリシー Wikipedioについて 免責事項 素数(そすう、Template:Lang-en-short)とは、1とその数自身以外に正の約数がない(つまり1とその数以外のどんな自然数によっても割り切れない)、1 より大きな自然数のこと。自然数や整数の積を考える上で基本的な構成要素であり、数論、暗号理論等において重要な役割を演ずる。
素数は無限に存在することが、紀元前3世紀頃のユークリッドの原論において既に証明されていた。100以下の素数を小さい順に列挙すると次の通り。 Template:Indent
100までの素数 | |||||||||
---|---|---|---|---|---|---|---|---|---|
Template:02 | 3 | Template:0Template:0 | Template:05 | Template:0Template:0 | 7 | Template:0Template:0 | Template:0Template:0 | ||
11 | 13 | 17 | 19 | ||||||
23 | 29 | ||||||||
31 | 37 | ||||||||
41 | 43 | 47 | |||||||
53 | 59 | ||||||||
61 | 67 | ||||||||
71 | 73 | 79 | |||||||
83 | 89 | ||||||||
97 |
整数の中で、あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想のような現代数学の重要な問題との興味深い結びつきが発見されている。
2008年8月、史上最大の素数探求のための分散コンピューティング・プロジェクトであるGIMPSによって、その時点で史上最大とされる素数が発見された。これは2009年10月現在において知られている中で47番目のメルセンヌ素数、243112609 - 1 であり、十進記数法で表記したときの桁数は1297万8189桁に及ぶ<ref>The Prime Pages, The Top Ten Record Primes</ref>。
目次 |
素因数分解の一意性
どんな自然数も、素数の積に表すことができる。しかもその表し方は、かけ算の順序を入れ替えることを除けば一通りしかない(素因数分解の一意性、算術の基本定理)。このことから、素数は自然数の構成要素としての役割を果たしていると見ることができる。つまり、素数の全体は、自然数の乗法に関して自然数全体の成す集合を生成する最小の生成系になる。
素数の定義である「1 とそれ自身でしか割り切れない」という条件(既約性)は、抽象代数学において、環の既約元の概念(一部の環では素元の概念と一致する)に抽象化され一般的に取り扱われる。一般の環の理論の中で、既約元によって全体が生成され、その表示が一意的に決まるという性質は稀有なものである。たとえばネーター環に分類される環ではいつでも各元の既約元分解ができるが、しかし既約元分解の表示が一意でないネーター環の例はいくつも知られている。一意的な既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。
素数の無限性
素数が無限に存在することはすでに古代ギリシャ時代から知られていて、ユークリッドが彼の著作『原論』<ref>日本語訳、中村幸四郎、寺阪英孝、池田美恵、伊東俊太郎『ユークリッド原論』共立出版 ISBN 4-320-01513-4</ref>の中で証明している。
- ユークリッドによる証明
- 背理法による。
- 素数が有限個しかないと仮定し、それらを次のようにおく。
- <math>p_i , i\le n</math>
- ただし n は定数。
- <math> q= p_1 p_2 p_3 \ldots p_n + 1</math>
- を考えよう。
- q は(有限と仮定した)全ての素数の積(自然数である)に1を足したものなのでやはり自然数であり、言いかえれば合成数であるか素数であるかのいずれかである。
- q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
- 一方、素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。
この証明方法以外にも
- 自然数の逆数の和が無限大に発散することを利用した証明<ref>レオンハルト・オイラーによる。現代的な用語で言えば、リーマンのゼータ関数のオイラー積表示を用いる。Ribenboim の第1章参照。</ref>
- 2つの異なるフェルマー数が互いに素であることを利用した証明<ref>Template:仮リンクによる。Ribenboim の第1章または "Proof from the Book" の第1章を参照。</ref>
- 整数の集合に、等差数列の族を開基とする位相を入れる証明<ref>ヒレル・ファステンバーグによる。en:Furstenberg's proof of the infinitude of primesを参照。</ref>
などが存在する。
素数の分布
素数のない、いくらでも長い区間が存在する。例えば、100! + 2 から 100! + 100 までの自然数はそれぞれ 2, …, 100 で割り切れるので、どれも素数ではない。同様に、任意に大きな n に対して n! + 2 から n! + n までは全て合成数である。比較的小さな数では、114から126まで13個連続で合成数となる。
ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。これに関して、次の素数定理は有名である。この定理は1896年に、アダマールとド・ラ・ヴァレ・プサンによって独立に証明された。
x 以下の素数の数を π(x) と表すとき、 Template:Indent この定理は、1792年に15歳のカール・フリードリッヒ・ガウスによって予想されていたものである(ガウスが最初に予想したのかどうかは不明)。この定理の証明は、ゼータ関数と複素関数論を用いる高度なものであったが、1949年にアトル・セルバーグとポール・エルデシュは独立に初等的な証明を与えた。この評価式はリーマン予想を仮定すると大幅に精度をよくすることができる。
次のような定理もある。
任意の自然数 n に対して n と 2n の間には素数が存在する。これは、ベルトランの仮説もしくはチェビシェフの定理と呼ばれる。この主張は、任意の素数 n の次の素数は 2n よりも小さい、とも言い換えられる。したがって、現在確認されている最大の素数 243112609 - 1 の次の素数は 243112610 - 2 よりも小さいということになる。
しかしながら、たとえば n2 と(n + 1)2 の間に素数が存在するかという問題は未解決である。
素数に関連する主な性質
- 素数の逆数の和は発散する(後述)。
- (a, m) = 1 のとき、等差数列
- a, a + m, a + 2m, …
- の中には無数の素数が含まれている。これはディリクレの算術級数定理と呼ばれる。
- 素数pを法とする合同に関して、フェルマーの小定理
- (a, p) = 1 ⇒ ap-1 ≡ 1 (mod p)
が成り立つ。
素数生成式
オイラーの発見した式、f(n) = n2 + n + 41 は、n = 0, …, 39 において全て素数となる。これは、虚二次体 <math>\mathbb{Q}(\sqrt{-163})</math> の類数が 1 であることと関係している<ref>Ribenboim 第3章</ref>。
多変数の高次多項式では、全ての素数を生成することができる式がいくつか知られている。例えば、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>: Template:Indent
素数の逆数和
素数の逆数の和は発散する。つまりどんな数よりも大きくなる。この命題は『素数が無数に存在する』という命題を含んでいる(有限個しかないならば発散しないはずである)が、それだけではなく素数の分布に関してより多くの情報を提供している。
この結果は最初にレオンハルト・オイラーによってゼータ関数を研究することでもたらされた。以下のものはポール・エルデシュによる、より直接で、また簡潔な証明である<ref>"Proofs from the Book" 第1章を参照。原論文は P. Erdös, "Über die Reihe ∑ 1/p", Mathematica, Zutphen B 7(1938), 1-2.</ref>。素数が無限個存在することは証明に用いないため、そのことの別証明にもなっている。
エルデシュによる証明
- 背理法による。
- 素数の逆数の和が収束すると仮定すると、任意の ε に対してある n が存在して、
- 1/pn+1 + 1/pn+2 + 1/pn+3 + ... < ε
- となる。いま、 ε を 1/2 としよう。任意の自然数 N に対して
- N/pn+1 + N/pn+2 + N/pn+3 + ... < N/2 ----- (1)
- を得る。1 から N までの N 個の数を 2 種類に分ける。N1をp1, p2,..., pnの中にしか約数を持たない数の個数とし、N2 は、pn+1,... のすくなくとも一つを約数に持つ数の個数とする。
- 構成から N = N1 + N2 ----- (2) である。ところが、以下に示すように十分 N を大きくとれば、N > N1 + N2 となる。
- [N/pn+1] + [N/pn+2] + [N/pn+3] + ... < N/2
- は (1) からいえる。ただし [N] はガウス記号で、 N を超えない最大の整数を表す。
- [N/p] が N 以下の p の正の倍数の個数を表すことに注意しよう。ここから
- N2 ≤ [N/pn+1] + [N/pn+2] + [N/pn+3] + ... < N/2
- が導かれる。よって、N2 < N/2
- あとは N1 を上から評価すればよいが、そのような数はすべて
- m = ai bi2
- の形にかける。ただし、 ai には、どの素数も 2 乗以上の部分は現われないようにできる。従って、可能な ai の数は 2n 通りであり、 bi は、
- bi ≤ √m ≤ √N
- であるから、結局可能な m の数は N1 ≤ 2n √N
- 示したいのはN1 < N/2 で、 2n+1 < √N が成り立てばよいが、そのためには N = 22(n+1) + 1 とすれば十分。
- よって N1 < N/2 であり、結局 N1 + N 2 < N となるが、これは (2) に反する。よって矛盾。
- Q.E.D.
特殊な形をした素数
- メルセンヌ素数: 2n − 1
- フェルマー素数: <math>2^{2^n}+1</math>
- オイラー素数: n2 + n + 41
- n! + 1 (n = 1, 2, 3, 11, 27, 37, 41, 73, 77, 116, 154, ...)
- n! − 1 (n = 3, 4, 6, 7, 12, 14, 30, 32, 33, 38, 94, 166, ...)
- #n ± 1 ( #n は n までの素数の積)
- レピュニット R2, R19, R23 ... (Rn は 1 が n 個続く数、通常は基数を 10 にとる)
- 双子素数: n と n + 2 がともに素数であるとき、これらは双子素数であるという。
- ソフィー・ジェルマン素数: n と 2n + 1 がともに素数であるとき、nをソフィー・ジェルマン素数という。
- ラマヌジャン素数
素数に関連する未解決の問題
- 双子素数の予想: 双子素数は無限に存在する、という予想。
- ゴールドバッハの予想: 6 以上の全ての偶数は 2 つの奇素数の和で表す事が出来る、という予想。
- フェルマー素数は無限に存在するか?
- メルセンヌ素数は無限に存在するか?
- ソフィー・ジェルマン素数は無限に存在するか?
- フィボナッチ数列には無限に素数が出現するか?
- n2 + 1 の形の素数は無限に存在するか?
- 全ての n に対し、n2 と (n + 1)2 の間に素数が存在するか?
語呂合わせ
整数の平方根や円周率などのように、素数にも語呂合わせによる記憶術がある。以下に挙げる。
- 100未満まで
- 兄さん(2、3) 5時に(5) セブンイレブン(7、11) 父さん(13) いいなと(17) ついていく(19) 兄さん(23) 買った肉を(29) 裂いて(31) みんなで食べたら(37) 41円しか(41) 予算がない(43) しなった顔で(47) ごみ拾い(53) ゴクっとのんで(59) 六井さんが(61) むなしく(67) 泣いた(71) ナミが(73) 泣く泣く(79) 破産した(83) 白紙に戻した(89) 宮内庁(97)
脚注
Template:脚注ヘルプ Template:Reflist
関連項目
参考文献
- 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
外部リンク
af:Priemgetal an:Numero primero ang:Frumtæl ar:عدد أولي arz:عدد اولى az:Sadə ədəd bat-smg:Pėrmėnis skaitlios be-x-old:Просты лік bg:Просто число bn:মৌলিক সংখ্যা br:Niver kentael bs:Prost broj ca:Nombre primer cs:Prvočíslo cy:Rhif cysefin da:Primtal de:Primzahl el:Πρώτος αριθμός en:Prime number eo:Primo es:Número primo et:Algarv eu:Zenbaki lehen fa:عدد اول fi:Alkuluku fr:Nombre premier ga:Uimhir phríomha gan:質數 gl:Número primo haw:Helu kumu he:מספר ראשוני hi:अभाज्य संख्या hr:Prost broj hsb:Primowa ličba ht:Nonm premye hu:Prímszámok hy:Պարզ թիվ id:Bilangan prima is:Frumtala (stærðfræði) it:Numero primo jbo:nalfendi kacna'u jv:Angka prima ka:მარტივი რიცხვი kn:ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆ ko:소수 (수론) ku:Hejmarên hîmî la:Numerus primus lb:Primzuel lmo:Nümar primm lt:Pirminis skaičius lv:Pirmskaitlis ml:അഭാജ്യസംഖ്യ mn:Энгийн тоо mr:मूळ संख्या ms:Nombor perdana nds:Primtall nl:Priemgetal nn:Primtal no:Primtall pl:Liczba pierwsza pms:Nùmer prim pnb:Prime number pt:Número primo ro:Număr prim ru:Простое число scn:Nùmmuru primu sh:Prost broj si:ප්රථමික සංඛ්යා simple:Prime number sk:Prvočíslo sl:Praštevilo sq:Numri i thjeshtë sr:Прост број sv:Primtal sw:Namba tasa szl:Pjyrszo nůmera ta:பகா எண் th:จำนวนเฉพาะ tr:Asal sayılar uk:Просте число ur:اولی عدد uz:Tub son vi:Số nguyên tố vls:Priemgetal war:Primo nga ihap xal:Экн тойг yi:פרימצאל yo:Nọ́mbà àkọ́kọ́ zh:素数 zh-classical:質數 zh-min-nan:Sò͘-sò͘ zh-yue:質數