素数

素数の最新ニュースをまとめて検索！

曖昧さ回避 この項目では、数学における素数について記述しています。日本の化粧品会社の社名については「素数 (企業)」をご覧ください。

素数（そすう、英: prime number）とは、1とその数自身以外に正の約数がない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のこと。自然数や整数の積を考える上で基本的な構成要素であり、数論、暗号理論等において重要な役割を演ずる。

素数は無限に存在することが、紀元前3世紀頃のユークリッドの原論において既に証明されていた。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, …（オンライン整数列大辞典の数列 A40）

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

2008年8月、史上最大の素数探求のための分散コンピューティング・プロジェクトであるGIMPSによって、その時点で史上最大とされる素数が発見された。これは2009年10月現在において知られている中で47番目のメルセンヌ素数、243112609 - 1 であり、十進記数法で表記したときの桁数は1297万8189桁に及ぶ[1]。

目次

[編集] 素因数分解の一意性

どんな自然数も、素数の積に表すことができる。しかもその表し方は、かけ算の順序を入れ替えることを除けば一通りしかない（素因数分解の一意性、算術の基本定理）。このことから、素数は自然数の構成要素としての役割を果たしていると見ることができる。つまり、素数の全体は、自然数の乗法に関して自然数全体の成す集合を生成する最小の生成系になる。

素数の定義である「1 とそれ自身でしか割り切れない」という条件（既約性）は、抽象代数学において、環の既約元の概念（一部の環では素元の概念と一致する）に抽象化され一般的に取り扱われる。一般の環の理論の中で、既約元によって全体が生成され、その表示が一意的に決まるという性質は稀有なものである。たとえばネーター環に分類される環ではいつでも各元の既約元分解ができるが、しかし既約元分解の表示が一意でないネーター環の例はいくつも知られている。一意的な既約元分解ができる環は一意分解環と呼ばれ、既約元分解は素元分解ともなる。

[編集] 素数の無限性

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

ユークリッドによる証明
背理法による。
素数が有限個しかないと仮定し、それらを次のようにおく。
p_i , i\le n
ただし n は定数。
q= p_1 p_2 p_3 \ldots p_n + 1
を考えよう。
q は(有限と仮定した)全ての素数の積（自然数である）に1を足したものなのでやはり自然数であり、言いかえれば合成数であるか素数であるかのいずれかである。
q が合成数だとすると q は pi のいずれかを用いて積の形に表されるはずである。その一方で q は pi のいずれで割っても 1 があまり、矛盾する。
一方、素数だとすると、これは pi のいずれとも異なるから素数が有限個しかないことに反する。

この証明方法以外にも

  • 自然数の逆数の和が無限大に発散することを利用した証明[3]
  • 2つの異なるフェルマー数が互いに素であることを利用した証明[4]

などが存在する。

[編集] 素数の分布

素数のない、いくらでも長い区間が存在する。例えば、100! + 2 から 100! + 100 までの自然数はそれぞれ 2, …, 100 で割り切れるので、どれも素数ではない。同様に、任意に大きな n に対して n! + 2 から n! + n までは全て合成数である。比較的小さな数では、114から126まで13個連続で合成数となる。

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

x 以下の素数の数を π（x） と表すとき、

\pi (x) \sim \int_{2}^x \frac{dt}{\log t} \sim \frac{x}{\log x}\qquad (x\to \infty)

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

次のような定理もある。

任意の自然数 n に対して n と 2n の間には素数が存在する。これは、ベルトランの仮説もしくはチェビシェフの定理と呼ばれる。この主張は、任意の素数 n の次の素数は 2n よりも小さい、とも言い換えられる。したがって、現在確認されている最大の素数 243112609 - 1 の次の素数は 243112610 - 2 よりも小さいということになる。

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

[編集] 素数に関連する主な性質

が成り立つ。

[編集] 素数生成式

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

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

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

[編集] 素数の逆数和

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

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

エルデシュによる証明

背理法による。
素数の逆数の和が収束すると仮定すると、任意の ε に対してある 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
示したいのは < N/2 で、それは 2n+1 < √N と同じであるが、そのためには N = 22（n+1） + 1 とすれば十分。
よって N1 < N/2 であり、結局 N1 + N 2 < N となるが、これは （2） に反する。よって矛盾。
Q.E.D.

[編集] 特殊な形をした素数

[編集] 素数に関連する未解決の問題

[編集] 語呂合わせ

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

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)

[編集] 脚注

[ヘルプ]
  1. ^ The Prime Pages, The Top Ten Record Primes
  2. ^ 日本語訳、中村幸四郎、寺阪英孝、池田美恵、伊東俊太郎『ユークリッド原論』共立出版 ISBN 4-320-01513-4
  3. ^ レオンハルト・オイラーによる。現代的な用語で言えば、リーマンのゼータ関数のオイラー積表示を用いる。Ribenboim の第1章参照。
  4. ^ ジョージ・ポーヤ（英語）による。Ribenboim の第1章または "Proof from the Book" の第1章を参照。
  5. ^ Ribenboim 第3章
  6. ^ 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
  7. ^ "Proofs from the Book" 第1章を参照。原論文は P. Erdös, "Über die Reihe ∑ 1/p", Mathematica, Zutphen B 7（1938), 1-2.

[編集] 関連項目

[編集] 参考文献

  • 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

[編集] 外部リンク

pnb:Prime number

"http://wkp.fresheye.com/wikipedia/%E7%B4%A0%E6%95%B0" より作成
フリー百科事典『ウィキペディア（Wikipedia）』 Text is available under GNU Free Documentation License.

最終更新 2009年11月11日 (水) 06:40 （日時は個人設定で未設定ならばUTC）。
【素数】変更履歴

ご利用上の注意

もっと調べる！

素数　まとめて検索