前のページ 1/3 次のページ

素数(そすう、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, …()

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

2008年8月、史上最大の素数探求のための分散コンピューティング・プロジェクトであるGIMPSによって、その時点で史上最大とされる素数が発見された。これは知られている中で46番目のメルセンヌ素数、2^43112609 - 1 であり、十進記数法で表記したときの桁数は1297万8189桁に及ぶ。指数で表記すると 2^43112609 - 1 ≒ 3.1647×10^12978188となる2^43112609 - 1 の[外部リンク] 十進数表示。データ量が大きく、表示に時間がかかるので注意。。

◆ 素因数分解の一意性

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

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

◆ 素数の無限性

素数が無限に存在することはすでに古代ギリシャ時代から知られていて、ユークリッドが彼の著作『原論』日本語訳、中村幸四郎、寺阪英孝、池田美恵、伊東俊太郎『ユークリッド原論』共立出版 ISBN 4-320-01513-4の中で証明している。

; ユークリッドによる証明

: 背理法による。

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

: $p\_i\; ,\; i\backslash le\; n$

: ただし n は定数。

: $q=\; p\_1\; p\_2\; p\_3\; \backslash ldots\; p\_n\; +\; 1$

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

: q が合成数だとすると q は $p\_i$ のいずれかを用いて積の形に表されるはずである。その一方で q は $p\_i$ のいずれで割っても 1 があまり、矛盾する。

: 一方、素数だとすると、これは $p\_i$ のいずれとも異なるから素数が有限個しかないことに反する。

この証明方法以外にも

・自然数の逆数の和が∞に発散することを利用した証明レオンハルト・オイラーによる。現代的な用語で言えば、リーマンのゼータ関数のオイラー積表示を用いる。Ribenboim の第1章参照。

・2つの異なるフェルマー数が互いに素であることを利用した証明ジョージ・ポーヤ () による。Ribenboim の第1章または "Proof from the Book" の第1章を参照。

などが存在する。

◆ 素数の分布

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

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

・x 以下の素数の数を π(x) と表すとき、

:$\backslash pi\; (x)\; \backslash sim\; \backslash int\_^x\; \backslash frac\backslash sim\; \backslash frac\backslash qquad\; (x\backslash to\; \backslash infty)$

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

次のような定理もある。

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

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

◆ 素数に関連する主な性質

・素数の逆数の和は発散する(後述)。

・(a, m) = 1 のとき、等差数列

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

:の中には無数の素数が含まれている。これはディリクレの算術級数定理と呼ばれる。

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

:(a, p) = 1 ⇒ a^p-1 ≡ 1 (mod p)

が成り立つ。

◆ 素数生成式

前のページ 1/3 次のページ

・素数 page1

・素数 page2

・素数 page3