素数

素数（そすう）は、単数であり単位元である １とそれ自身でしか割り切れない数。数の原子とも言われる基本的な数。通常は、自然数の範囲で考えるが、整数や複素数の範囲で考える人もいるとか。また、剰余系を考えると「0 とか 1 とかも〚素数〛に含めちゃった理論」があっても一向に構わないはずだが、「それで面白い結果が出てくるとは思えない」のでやらないという、数学会のピン芸人としての数学者としての美学に反するらしく、マトモな数学者は誰もやらない。とはいえ芸人たるもの「『マトモ』に縛られていたら芸人ではない」という振りきれちゃった数学者もおり、そうした“マトモでない数学者”も遠山啓ほか銀林浩・森毅など多く存在する。

一万未満(四桁以下)の素数

一万未満(四桁以下)の素数

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, 101, 103, 107, 109, 113, 139, 149, 151, 157, 127, 131, 137, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 841, 853, 857, 859, 883, 887, 907, 911, 863, 877, 881, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1189, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1681, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973

数学的な性質

素数は 2 を例外として常に奇数である。なお、素数の概念は環論における既約元または素元にあたる。
「素数が数直線上にどのように現れるか？」については判っていることが少ない。したがって、「ｎ番目の素数を簡単な式で表すことは不可能であろう」と予想されている。
例外的に証明されていて比較的に簡単なものとしては、「ベルトラン＝チェビシェフの定理」がある。本当のことをいうなら「ベルトラン仮説(ベルトラン予想)」が証明されて「チェビシェフの定理」になったのだが、チェビシェフは多才であったため「ベルトラン＝チェビシェフの定理」とされる。これは「素数 p があったとして、p より大きく 2p より小さい素数 p' が必ずある」というもので、ベルトランが仮説として提出したものにチェビシェフがΓ関数(階乗の定義域を実数まで拡張したもの)を用いて証明した。ただし「Γ関数」がわからんという人も多かったようで、ポール・エルデーシュが高校生のときに初等的な証明を行なったと云われている。その後、一松信がエルデーシュの証明を見直して、さらに分かりやすくした。

未解決問題

上記のように、素数に関する多くの未解決問題がある。

双子素数問題

3 以上の素数はすべて奇数(奇素数)であるためその差は常に偶数なのだが、「最小の偶数 2 が差である素数のペア(p, p+2)は無限にあるか？」は未解決である。

ゴールドバッハの予想

「6 以上の偶数は、必ず 2 つの奇素数の和で表される」というもの。これが正しかったらペルトラン＝チェビシェフの定理はほとんど自明である。

シェルピンスキーの問題

正式な命名ではない。シェルピンスキーの『ピタゴラスの三角形』という本に出てくる。「奇素数を自乗して１を足してから２で割ったものが、やっぱり素数になる素数は無限にあるか？」である。たぶん三十年以上は未解決である。「いくつ連鎖するか？」という興味もある。とりあえず p < 100 の範囲で調べてみると、

• 3 ⇒ 5 ⇒ 13
• 11 ⇒ 61 ⇒ 1861
• 19 ⇒ 181
• 41 ⇒ 841
• 59 ⇒ 1741
• 71 ⇒ 2521
• 79 ⇒ 3121

といった感じになる。

リーマン予想

「リーマン予想」の項を参照のこと。

素数の発見

素数は無限に存在するが、規則性がないため、「人類が誰も知らない新しい素数」を求めようとするとひたすら計算するしかない。

ただし、自然数も素数も無限にあるので数えきることはできないが、自然数の中にどれぐらいの割合で素数があるかは対数関数などを使って計算可能。この割合の予想は、小さな数では誤差が大きいが十分に範囲を大きくするとかなりの精度で一致する。これは素数階段などの概念と関係する。

新しい素数の発見は暗号理論の発展にもつながるため、市民参加型の素数発見プロジェクト「メルセンヌ巨大素数検索プロジェクト（GIMPS：Great Internet Mersenne Prime Search）が存在し、新しい素数の発見者にはGIMPSから賞金3000ドルが授与される。インターネットにつながっているコンピュータさえあれば、ソフトをインストールするだけであなたも今すぐにGIMPSの素数発見作業に参加することができる。2017年末時点で人類が知る最大の素数は、GIMPSが発見した「2324万9425桁」の素数である。なお、テキストファイルのZIP圧縮状態で24MBになるこの素数は「そのまま」書籍として販売されている（虹色社『2017年最大の素数』ISBN 978-4909045072）。2024 に記録は GIMPS により更新され、2^136279841 - 1 となった。桁数は 41014320 桁でそうで、136279841 * log[10](2) で計算してみたら末尾が 20 ではなく 19.95 とかになった。この場合は切り上げで20とする。

これとは別に、電子フロンティア財団は1億桁以上の素数に15万ドルの懸賞金を提示している。100万桁以上の素数には5万ドル、1000万桁以上の素数には10万ドルの懸賞金が提示され、それぞれ最初の発見者（どちらもGIMPSの参加者）に授与された。

素数生成式

この関数を用いることで、n番目の素数を数式で表すことも可能である。しかし、ただでさえ計算量が多すぎる素数判定関数を繰り返し用いて、範囲内の全ての素数を書き出したものに、「n番目であるかどうか」の判定を嚙ませているだけなので、実用性は全くない。この式を用いてスーパーコンピューターで計算するよりも、エラトステネスの篩|エラトステネスの篩にかけたほうが速いほどである。

${\begin{aligned}p_{n}&=\sum _{i=2}^{2^{n}}i\mathrm {P} (i)\delta _{n-1}^{\left(\displaystyle \sum _{j=2}^{i-1}\mathrm {P} (j)\right)}\\&=\sum _{i=2}^{2^{n}}i\prod _{k_{1}=2}^{i-1}\left(1-\sum _{k_{2}=1}^{i}\delta _{k_{1}k_{2}}^{i}\right)\delta _{n-1}^{\left\{\displaystyle \sum _{j=2}^{i-1}\prod _{k_{3}=2}^{j-1}\left(1-\sum _{k_{4}=1}^{j}\delta _{k_{3}k_{4}}^{j}\right)\right\}}\end{aligned}}$

なお、「素数生成多項式」は存在しないことが証明されている。

エラトステネスの篩

まず２が最小の素数だということを認めようそこで {2} という「２以下のすべての素数を網羅した表」ができる。
３は２の次の数である。3 は２以下のすべての素数によって割り切れないので素数である。そこで {2, 3} という新しい表ができる。こうして「 n 未満の数の表のすべての要素によって割り切れない」数のみを救い上げて、そうでない数をふるい落としてゆくので「エラトステネスの篩」の名がついた。この表のうち、最大の項の自乗よりも小さい数はすべてこの篩に引っかからないので、この表はそこまで使える。これを繰り返してゆけば、この「 n 以下のすべての素数を網羅した表」は大きくなってゆくので、到達できる範囲は広くなってゆく。
素朴な方法だが、昨今のパソコンであれば、一万くらいは簡単に求まる。どうせデスクトップ・パソコンなんかは動作中でも「人間の応答を待つ」くらいしか仕事はしていないので、人間様が寝ている間に粛々と素数を計算していてもらってもいいと思う。

素数判定関数

nが素数なら1、合成数なら0を返す関数 P(n) を作ること自体は可能であり、いくつもの手法が開発されている。実用性は全くないとも言われるが、「結婚披露宴の ご祝儀は割り切れると験が悪い」というので「二万円ではなく三万円」というのが一般常識とされるが、「“二万を越える最小の素数”円」ならかなり節約できる。

一例。ここで $\delta _{j}^{i}$ はクロネッカーのデルタ（i = j のとき 1 、 i ≠ j のとき 0）

$\mathrm {P} (n)=\prod _{k_{1}=2}^{n-1}\left(1-\sum _{k_{2}=1}^{n}\delta _{k_{1}k_{2}}^{n}\right)$

総乗を2回用いるもの（一例）や、正弦関数と天井関数を用いたもの（一例）も考案されている。

素数表現多項式

各変数に0以上の整数を代入すると、必ず素数が得られる数式も存在する。n番目の素数を表せるわけではなく、計算量も多いため、実用性は全くない。ロシアの数学者、ユーリ・マチャセビッチによる「マチャセビッチの多項式」が主に知られている。以下はAからZまでの26変数を用いるものであるが、マチャセビッチは19変数のものも考案している。

${\begin{aligned}(K+2)(1&-[WZ+H+J-Q]^{2}\\&-[(GK+2G+K+1)(H+J)+H-Z]^{2}\\&-[16(K+1)^{3}(K+2)(N+1)^{2}+1-F^{2}]^{2}\\&-[2N+P+Q+Z-E]^{2}\\&-[E^{3}(E+2)(A+1)^{2}+1-O^{2}]^{2}\\&-[(A^{2}-1)Y^{2}+1-X^{2}]^{2}\\&-[16R^{2}Y^{4}(A^{2}-1)+1-U^{2}]^{2}\\&-[N+L+V-Y]^{2}\\&-[(A^{2}-1)L^{2}+1-M^{2}]^{2}\\&-[AI+K+1-L-I]^{2}\\&-[((A+U^{2}(U^{2}-A))^{2}-1)(N+4DY)^{2}+1-(X+CU)^{2}]^{2}\\&-[P+L(A-N-1)+B(2AN+2A-N^{2}-2N-2)-M]^{2}\\&-[Q+Y(A-P-1)+S(2AP+2A-P^{2}-2P-2)-X]^{2}\\&-[Z+PL(A-P)+T(2AP-P^{2}-1)-PM]^{2})\end{aligned}}$

（この数式で表される数が負でないとき、その数は素数である）

人間生活との関わり・利用

大きな数の素因数分解は困難であるため、暗号理論に応用されている。
未解決問題が多いため、ややこしい神秘的な数とする人もいる。

関連項目

• 素因数分解
• 双子素数
• 「ゴルトバッハ予想(ゴールドバッハの予想)」
• 素数計数関数

外部リンク

• 1000万までの素数の一覧