メルセンヌ素数チェッカー

指定された指数 p に対して 2^p − 1 がメルセンヌ素数であるかどうかを判定します。アニメーション化された反復トレースを伴うリュカ–レーマー・プリマリティ・テスト、バイナリ・ビットパターン可視化、ユークリッド–オイラーの完全数のペアリング、および既知の52個のメルセンヌ素数に関する歴史的背景を使用します。

メルセンヌ素数チェッカー

Embed メルセンヌ素数チェッカー Widget

メルセンヌ素数チェッカー

メルセンヌ素数チェッカーへようこそ。このインタラクティブなツールは、5000 までの指数 $p$ に対して、$2^p - 1$ がメルセンヌ素数であるかどうかをテストします。このツールは、有名なリュカ・レーマー・テストを実行し、漸化式 $S_i = S_{i-1}^2 - 2 \pmod{M_p}$ のアニメーション付き反復トレースを表示し、（すべてのメルセンヌ数の決定的な特徴である）2 進数ビットパターンを視覚化します。また、結果が素数の場合は、ユークリッド・オイラーの定理に基づいて対応する偶数の完全数も表示します。

メルセンヌ素数とは？

メルセンヌ数とは、$M_p = 2^p - 1$ の形式で表される数です。$M_p$ 自体が素数である場合、それはメルセンヌ素数と呼ばれます。名前の由来は、初期の事例をカタログ化し、257 までの指数のうちどれが素数になるかを推測したフランスの修道士マリン・メルセンヌ（1588-1648）にちなんでいます。彼のリストの一部は間違っていることが判明しましたが、3 世紀にわたる研究のきっかけとなりました。

メルセンヌ素数

$$M_p = 2^p - 1 \;\; \text{が素数であるとき（ここで } p \text{ 自体も素数である必要があります）}$$

最初の数個のメルセンヌ素数は以下の通りです：

$M_2 = 3$
$M_3 = 7$
$M_5 = 31$
$M_7 = 127$
$M_{13} = 8{,}191$
$M_{17} = 131{,}071$
$M_{19} = 524{,}287$
$M_{31} = 2{,}147{,}483{,}647$ （1772年にオイラーによって発見され、104年間既知の最大の素数でした）

2024年現在、正確に 52個のメルセンヌ素数が知られています。現在の記録は、2024年10月に GIMPS 分散コンピューティングプロジェクトによって発見された $M_{136{,}279{,}841}$ で、41,024,320 桁の 10 進数です。

リュカ・レーマー・テスト

メルセンヌ素数が素数記録の大部分を占める理由は、エドゥアール・リュカ（1878年）によって発見され、デリック・レーマー（1930年）によって簡略化された、この特殊で極めて高速な素数判定法にあります：

リュカ・レーマー・テスト

$$S_0 = 4, \quad S_i = S_{i-1}^2 - 2 \pmod{M_p}$$

素数 $p \geq 3$ に対して：$\;M_p$ が素数 $\iff S_{p-2} \equiv 0 \pmod{M_p}$

このテストでは $p-2$ 回のモジュロ自乗演算のみが必要です。これは、通常の筆算による乗算では $O(p^3)$ ビット演算、FFT を使用した場合は $O(p^2 \log p \log\log p)$ で済みます。これを、何百万桁もの $M_p$ クラスの数に対する汎用的な素数判定法（完全に実行不可能）と比較してください。リュカ・レーマーの近道こそが、メルセンヌ素数の探索を可能にしているのです。

なぜ $p$ は素数でなければならないのか？

$p = a \cdot b$ かつ $a, b > 1$ の場合、典型的な恒等式によって $2^a - 1$ が $2^{ab} - 1$ を割り切ることが示されます：

因数分解の恒等式

$$2^{ab} - 1 = (2^a - 1)\left(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1\right)$$

したがって、指数が合成数の場合、$M_p$ は自動的に合成数となります。逆は成り立ちません： $p$ が素数であっても、$M_p$ が素数であることを保証するものではありません。例えば、$p = 11$ は素数ですが、$M_{11} = 2047 = 23 \times 89$ となります。

メルセンヌ素数と完全数（ユークリッド・オイラー）

紀元前 300 年頃、ユークリッドは $2^p - 1$ が素数であれば、$2^{p-1}(2^p - 1)$ は完全数（その数自身を除く正の約数の和が、その数自身に等しい数）であることを発見しました。後にオイラーは、すべての偶数の完全数がこの形式であることを証明しました。

ユークリッド・オイラーの定理

$$N \text{ が偶数の完全数である} \iff N = 2^{p-1}(2^p - 1),\;\; 2^p - 1 \text{ は素数}$$

つまり、新しいメルセンヌ素数が見つかることは、即座に新しい完全数が見つかることを意味します。最初の 4 つの偶数の完全数は 6, 28, 496, 8128 であり、古代から知られています。奇数の完全数が存在するかどうかは、2,300 年以上経った今でも未解決の問題です。

2 進数ビットパターン

すべてのメルセンヌ数は、非常にクリーンな 2 進数表現を持っています。2 進数での $2^p$ は 1 の後に $p$ 個の 0 が続くため、$2^p - 1$ は正確に $p$ 個の連続した 1 になります：

M_5 = 2^5 − 1 = 11111₂ = 31

M_7 = 2^7 − 1 = 1111111₂ = 127

このため、このツールは各ビットを独自のタイルとして視覚化します。ビットパターンは、その数が素数であるかどうかに関わらず、メルセンヌ数の視覚的なサインとなります。

この電卓の使い方

指数 $p$ を入力： 1 から 5,000 までの正の整数。
「メルセンヌ素数をチェック」をクリック： ツールはまず $p$ が素数かどうかを確認し、そうでない場合はなぜ $M_p$ が合成数になるのかを説明します。
素数 $p$ の場合： リュカ・レーマー漸化式が $M_p$ を法として $p - 2$ 回反復されます。
出力を確認： 判定バナー、6 行の反復トレース（大きな $p$ の場合は中間のステップを「...」で省略）、$M_p$ の 10 進数および 2 進数形式、および該当する場合はユークリッド・オイラーの完全数のペアリングが表示されます。

既知のメルセンヌ素数（最初の 12 個）

#	指数 $p$	$M_p = 2^p - 1$	桁数	発見
1	2	3	1	古代
2	3	7	1	古代
3	5	31	2	古代
4	7	127	3	古代
5	13	8,191	4	1456年 (匿名)
6	17	131,071	6	1588年 Cataldi
7	19	524,287	6	1588年 Cataldi
8	31	2,147,483,647	10	1772年 Euler
9	61	2.3 × 10^18	19	1883年 Pervushin
10	89	6.2 × 10^26	27	1911年 Powers
11	107	1.6 × 10^32	33	1914年 Powers
12	127	1.7 × 10^38	39	1876年 Lucas

GIMPS プロジェクト

1996 年に George Woltman によって開始された Great Internet Mersenne Prime Search (GIMPS) は、ボランティアが CPU 時間を寄付して候補指数に対してリュカ・レーマー・テストを実行する分散コンピューティングプロジェクトです。2024年現在、M_35 = M_{1398269} (1996年) 以降のすべてのメルセンヌ素数は GIMPS によって発見されています。現代のフロンティア（$10^8$ 付近の指数）における 1 回のリュカ・レーマー・テストは、GPU を使用しても数週間の計算時間を要します。

メルセンヌ素数に関する豆知識

$M_{31} = 2{,}147{,}483{,}647$ は最大の 32 ビット符号付き整数であり、C 言語における有名な $\texttt{INT\_MAX}$ です。これは偶然ではありません。$M_{31}$ が素数であるため、自然な「オーバーフロー寸前」の境界として機能しているのです。
連続するメルセンヌ素数の間には未知の大きさのギャップがあります。メルセンヌ素数が無限に存在するかどうかはわかっていませんが、レンストラ・ポメランス・ワグスタッフの予想では、約 $e^\gamma \log_2 p$ の割合で増加し、無限に存在するとされています。
2008 年、電子フロンティア財団は 1000 万桁の素数を最初に発見した人に 10 万米ドルの賞金を授与しました。この賞金は $M_{43112609}$ を発見した UCLA の GIMPS チームに贈られました。最初の 1 億桁の素数発見者には、さらに 15 万米ドルの賞金が用意されています。
$M_{31}$ は、オイラーの発見を記念して 1811 年にロシアで発行された 100 ルーブル記念紙幣に描かれています。通貨に素数が印刷された数少ない例の一つです。
すべてのメルセンヌ素数が完全数を生み出すため、人類が現在把握している偶数の完全数は正確に 52 個（既知の 52 個のメルセンヌ素数に対応）存在します。

よくある質問

メルセンヌ素数とは何ですか？

メルセンヌ素数とは、$2^p - 1$ の形式で表される素数のことです（ここで $p$ も素数である必要があります）。最初の数個は 3, 7, 31, 127, 8,191 です。2024年現在、52 個のメルセンヌ素数が知られています。最大の既知の素数（$M_{136{,}279{,}841}$）は、4100 万桁を超えるメルセンヌ素数です。

リュカ・レーマー・テストはどのように機能しますか？

素数指数 $p \geq 3$ に対して、$S_0 = 4$ および $S_i = S_{i-1}^2 - 2 \pmod{M_p}$ と定義します。メルセンヌ数 $M_p = 2^p - 1$ が素数であるための必要十分条件は、$S_{p-2} \equiv 0 \pmod{M_p}$ であることです。テストは $p - 2$ 回の反復で実行され、それぞれが単一のモジュロ自乗演算です。

なぜ $p$ は素数でなければならないのですか？

もし $p = ab$ で両方の因数が 1 より大きい場合、$2^p - 1$ は $2^a - 1$（および $2^b - 1$）で割り切れるため、$M_p$ は合成数となります。逆は必ずしも真ではありません。$p$ が素数であっても $M_p$ が素数であるとは限りません。例えば $p = 11$ は素数ですが、$M_{11} = 2047 = 23 \times 89$ となり合成数です。

メルセンヌ素数と完全数の関係は何ですか？

ユークリッド・オイラーの定理によれば、すべての偶数の完全数は $2^{p-1}(2^p - 1)$ の形式を持ち、ここで $2^p - 1$ はメルセンヌ素数です。したがって、各メルセンヌ素数は正確に 1 つの偶数の完全数を生成し、すべての偶数の完全数はメルセンヌ素数から派生します。奇数の完全数が存在するかどうかは、数学における最も古い未解決問題の一つです。

なぜ $M_p$ は 2 進数で $p$ 個の連続した 1 になるのですか？

2 進数における $2^p$ は、1 の後に $p$ 個の 0 が続く数です。そこから 1 を引くと、末尾の $p$ 個の 0 がすべて 1 に変換されます。したがって、2 進数での $2^p - 1$ は正確に $p$ 個の 1 で構成されます。これは、素数か合成数かに関わらず、すべてのメルセンヌ数の視覚的な特徴です。

このツールでテストできる最大の指数は何ですか？

このツールは、通常の Web リクエスト内でリュカ・レーマー反復が完了するように、5,000 までの指数をテストします。それ以上の大きな指数（$10^8$ 付近の GIMPS フロンティアを含む）については、1 回のテストに現代の GPU でも数週間かかることがあるため、Prime95 などの専用ソフトウェアが必要です。