素数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

素数は無限に存在するが、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

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

2006年9月、史上最大の素数探求のための分散コンピューティング・プロジェクトであるGIMPSによって、現時点で史上最大とされる素数が発見された。これは44番目のメルセンヌ素数、2^32582657-1であり、十進記数法で表記したときの桁数は980万8,358桁に及ぶ。史上最大の素数は[1]に掲載、印刷すると紙およそ1800枚分になる。

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

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

[編集] 素数の無限性

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

ユークリッドによる証明

背理法による。

素数が有限個しかないと仮定し、それらを次のようにおく。

$p_i , i\le n$

ただし n は定数。

$q= p_1 p_2 p_3 \ldots p_n + 1$

を考えよう。q は合成数であるか素数であるかのいずれかである。

q が合成数だとすると q は

p i

のいずれかを用いて積の形に表されるはずである。その一方で q は

p i

のいずれで割っても 1 があまり、矛盾する。

素数だとすると、これは

p i

のいずれとも異なるから素数が有限個しかないことに反する。

Q.E.D.

この証明方法以外にも

自然数の逆数の和が∞に発散することを利用した証明
2つの異なるメルセンヌ数が互いに素であることを利用した証明

などが存在する。

[編集] 素数の分布

素数のない、いくらでも長い区間が存在する。例えば、100!+2 から 100!+100 までの自然数はそれぞれ 2,..,100 で割り切れるので、どれも素数ではない。

ある自然数までにどのくらいの素数があるのかという問題は、基本的だが非常に難しい問題である。これに関して、次の素数定理は有名である。この定理は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 の間には素数が存在する（1850年、チェビシェフ）

言い換えれば、任意の素数 n の次の素数は 2n よりも小さい、というのと同じことである。

したがって、現在確認されている最大の素数 2^32582657-1 の次の素数は 2^32582658-2 よりも小さいということになる。

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

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

素数の逆数の和は発散する。（後述）
（a,m）=1のとき、等差数列

a,a+m,a+2m,…

の中には無数の素数が含まれている。 (ディリクレの算術級数定理)

素数pを法とする合同に関して、フェルマーの小定理

（a,p）=1 ⇒　a^p-1≡1 （mod p）

が成り立つ。

[編集] 素数生成式

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

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

w z + h + j - q = 0

(g k + 2 g + k + 1)(h + j) + h - z = 0

(16 k + 1) 3 (k + 2)(n + 1) 2 + 1 - f 2 = 0

2 n + p + q + z - e = 0

e 3 (e + 2)(a + 1) 2 + 1 - o 2 = 0

(a 2 - 1) y 2 + 1 - x 2 = 0

16 r 2 y 4 (a 2 - 1) + 1 - u 2 = 0

n + l + v - y = 0

(a 2 - 1) l 2 + 1 - m 2 = 0

a i + k + 1 - l - i = 0

((a + u 2 (u 2 - a)) 2 - 1)(n + 4 d y) 2 + 1 - (x + c u) 2 = 0

p + l (a - n - 1) + b (2 a n + 2 a - n 2 - 2 n - 2) - m = 0

q + y (a - p - 1) + s (2 a p + 2 p - p 2 - 2 p - 2) - x = 0

z + p l (a - p) + t (2 a p - p 2 - 1) - p m = 0

[編集] 素数の逆数和

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

この結果は最初にレオンハルト・オイラーによってゼータ関数を研究することでもたらされた。我々がここで紹介するのは、ポール・エルデシュによる、より直接で、また簡潔な証明である。その上、無限個存在することも直接には使わない。

エルデシュによる証明

背理法による。

素数の逆数の和が収束すると仮定すると、任意の ε に対してある n が存在して、

1/p_n+1 + 1/p_n+2 + 1/p_n+3 + ... < ε

となる。いま、 ε を 1/2 としよう。任意の自然数 N に対して

N/p_n+1 + N/p_n+2 + N/p_n+3 + ... < N/2 ----- （1）

を得る。1 から N までの N 個の数を 2 種類に分ける。N₁をp₁, p₂,..., p_nの中にしか約数を持たない数の個数とし、N₂ は、p_n+1,... のすくなくとも一つを約数に持つ数の個数とする。

構成から N = N₁ + N₂ ----- （2）である。ところが、以下に示すように十分 N を大きくとれば、N > N₁ + N₂ となる。

[N/p_n+1] + [N/p_n+2] + [N/p_n+3] + ... < N/2

は（1）からいえる。ただし [N] はガウス記号で、 N を超えない最大の整数を表す。

[N/p] が N 以下の p の正の倍数の個数を表すことに注意しよう。ここから

N₂ ≤ [N/p_n+1] + [N/p_n+2] + [N/p_n+3] + ... < N/2

が導かれる。よって、N₂ < N/2

あとは N₁ を上から評価すればよいが、そのような数はすべて

m = a_i b_i²

の形にかける。ただし、 a_i には、どの素数も 2 乗以上の部分は現われないようにできる。従って、可能な a_i の数は 2ⁿ 通りであり、 b_i は、

b_i ≤ √m ≤ √N

であるから、結局可能な m の数は N₁ ≤ 2ⁿ √N

示したいのは < N/2 で、それは 2ⁿ⁺¹ < √N と同じであるが、そのためには N = 2^2（n+1） + 1 とすれば十分。

よって N₁ < N/2 であり、結局 N₁ + N ₂ < N となるが、これは（2）に反する。よって矛盾。

Q.E.D.

参考文献 M.アイグナー　G.M.ツィーグラー　蟹江幸博訳「天書の証明」　シュプリンガー・フェアラーク東京　第1章　素数は無限：6つの証明　第6の証明（ISBN 4-431-70986-X）
原論文は　P.Erdös "Über die Reihe ∑ 1/p" Mathematica, Zutphen B 7 （1938）, 1-2

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

メルセンヌ素数: 2ⁿ − 1
フェルマー素数: $2^{2^n}+1$
オイラー素数: n² + n + 41
n! + 1 （n = 1, 2, 3, 11, 13, 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 までの素数の積）
レピュニット R₂, R₁₉, R₂₃ ... （R_n は 1 が n 個続く数（基数10））
双子素数: n と n+2 がともに素数であるとき、これらは双子素数であるという。
ソフィー・ジェルマン素数: n と 2n+1がともに素数であるとき、nをソフィー・ジェルマン素数という。
ラマヌジャン素数

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

双子素数の予想:双子素数は無限に存在する、という予想。
ゴールドバッハの予想: 6 以上の全ての偶数は 2 つの奇素数の和で表す事が出来る、という予想。
フェルマー素数は無限に存在するか?
メルセンヌ素数は無限に存在するか?
ソフィー・ジェルマン素数は無限に存在するか?
フィボナッチ数列には無限に素数が出現するか?
n²+1 の形の素数は無限に存在するか?
全ての n に対し、n² と（n + 1）² の間に素数が存在するか？

[編集] 語呂合わせ

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

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)

[編集] 関連項目

[編集] 外部リンク

"http://ja.wikipedia.org../../../%E7%B4%A0/%E6%95%B0/_/%E7%B4%A0%E6%95%B0.html" より作成

カテゴリ: 初等数学 | 数論 | 計算数論 | 整数の類 | 数学に関する記事

素数