素数

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

素数（そすう、英: 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）

100までの素数
	02	3	00	05	00	7	00		00
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番目のメルセンヌ素数、2^43112609 - 1 であり、十進記数法で表記したときの桁数は1297万8189桁に及ぶ^[1]。

素因数分解の一意性

自然数に対して、算術の基本定理とも呼ばれる、「どんな自然数でも素数の積として表すことができ、その表し方はかけ算の順序を入れ替えることを除けば一通りしかない」という素因数分解の一意性が成立する。すなわち、「素数の全体」は自然数全体の成す集合を（乗法に関して）生成する最小の生成系である。俗な表現をすれば、これは「素数は自然数の構成要素としての役割を果たしている」というような意味と受け取ってよい。

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

素数の無限性

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

ユークリッドによる証明

背理法による。

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

${\displaystyle p_{i},i\leq n}$ 

ただし n は定数。

${\displaystyle q=p_{1}p_{2}p_{3}\ldots p_{n}+1}$ 

を考えよう。

q は(有限と仮定した)全ての素数の積（自然数である）に1を足したものなのでやはり自然数であり、言いかえれば合成数であるか素数であるかのいずれかである。

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

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

この証明方法以外にも

• 自然数の逆数の和が無限大に発散することを利用した証明^[3]
• 2つの異なるフェルマー数が互いに素であることを利用した証明^[4]
• 整数の集合に、等差数列の族を開基とする位相を入れる証明^[5]

などが存在する。

 

自然数を渦巻状に並べていき、素数だけを黒く塗ったもの。特徴的な模様が見える。(ウラムの螺旋)

素数の分布

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

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

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

${\displaystyle \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 よりも小さい、とも言い換えられる。したがって、現在確認されている最大の素数 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)　が成り立つ。
• 5以上の素数はすべて、自然数mを用いて6m+1または6m-1の形で表わすことができる（逆は成り立たない）。この性質を用いて素数関連の整数問題を解くのは受験生の必須事項である。

素数生成式

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

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

${\displaystyle wz+h+j-q=0}$ 
${\displaystyle (gk+2g+k+1)(h+j)+h-z=0}$ 
${\displaystyle (16k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}=0}$ 
${\displaystyle 2n+p+q+z-e=0}$ 
${\displaystyle e^{3}(e+2)(a+1)^{2}+1-o^{2}=0}$ 
${\displaystyle (a^{2}-1)y^{2}+1-x^{2}=0}$ 
${\displaystyle 16r^{2}y^{4}(a^{2}-1)+1-u^{2}=0}$ 
${\displaystyle n+l+v-y=0}$ 
${\displaystyle (a^{2}-1)l^{2}+1-m^{2}=0}$ 
${\displaystyle ai+k+1-l-i=0}$ 
${\displaystyle ((a+u^{2}(u^{2}-a))^{2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0}$ 
${\displaystyle p+l(a-n-1)+b(2an+2a-n^{2}-2n-2)-m=0}$ 
${\displaystyle q+y(a-p-1)+s(2ap+2p-p^{2}-2p-2)-x=0}$ 
${\displaystyle z+pl(a-p)+t(2ap-p^{2}-1)-pm=0}$ 

素数の逆数和

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

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

エルデシュによる証明

背理法による。

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

1/pn+1 + 1/pn+2 + 1/pn+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,... の少なくとも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₁ < N/2 で、 2ⁿ⁺¹ < √N が成り立てばよいが、そのためには N = 2^2（n+1） + 1 とすれば十分。

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

Q.E.D.

特殊な形をした素数

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

素数に関連する未解決の問題

• 双子素数の予想: 双子素数は無限に存在する、という予想。
• ゴールドバッハの予想: 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)

37未満まで

兄さん(2、3) 5時に(5) セブンイレブン(7、11) 父さん(13) いないけど(17) 行く(19) 兄さん(23) 肉持って(29) サーティーワン(31)

脚注

[脚注の使い方]

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. ^ ヒレル・ファステンバーグによる。en:Furstenberg's proof of the infinitude of primesを参照。
6. ^ Ribenboim 第3章
7. ^ 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
8. ^ "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

外部リンク

• The Prime Page
• Weisstein, Eric W. “Prime Number”. mathworld.wolfram.com (英語).

Template:Link FA Template:Link FA ru Template:Link GA Template:Link GA