過去最大の素数が発見！

2024年10月，衝撃的なニュースが飛び込んできた．なんと，約6年ぶりに｢現時点で素数であることが分かっている具体的な最大の整数｣が更新されたのだ．この記事では，発見された素数を紹介するとともに，背景にある素数の知識や素数発見の最前線を解説する．

発見された｢最大の素数｣とは
現在発見されている素数の大きさランキング
2024年に見つかった素数
素数の定義
メルセンヌ素数
素数判定法
1. リュカ-レーマー･テスト
2. フェルマーテスト
メルセンヌ素数の歴史
メルセンヌ素数の一覧
素数の未解決問題
1. 素数に関する重要な未解決問題
2. メルセンヌ素数に関する未解決問題
GIMPSに参加してみよう
最後に
参考文献

発見された｢最大の素数｣とは

2024年10月12日，Luke Durant氏が新たな素数を発見した．
\[ 2^{136279841}-1\]
この素数は，10月19日にGIMPS(Great Internet Mersenne Prime Search)による検証が終了し，10月21日に発表された．

発見者Luke Durant氏は，アメリカのカリフォルニア州サンノゼ在住の36歳の研究者で，NVIDIAで勤務していたことにも注目が集まった．Luke Durant氏は，2017年に氏によって作成されたGPU上で動作するメルセンヌ素数探索のソフトウェアを利用し，数千台のサーバーGPUを使ってメルセンヌ素数の可能性を検証する，17カ国と24のデータセンターリージョンにまたがる大規模なシステムを構築した．
このシステムによる約1年の検証を経て，2024年10月11日に$2^{136279841}-1$が素数である可能性がフェルマーテストによって浮上し，10月12日，リュカ-レーマー･テストにより素数であることが判明した．その後，Luke Durant氏はGIMPSにこれを報告し，GIMPSによって複数のプログラム，複数のプラットフォームで厳密な検証を行い，素数であることが認められた．
そして，フェルマーテストによって素数の可能性が浮上した10月11日を発見日とするか，リュカ-レーマー･テストによって素数と判定された10月12日を発見日とするかが議論され，最終的に素数であることが判明した10月12日を公式の発見日とすることとなった．

この素数が発見されたというニュースは話題を呼び，｢最大の素数｣がXのトレンドにもなった．しかし，注意が必要なのは，今回見つかった素数は，あくまでも｢現時点で素数であることが分かっている具体的な整数のうち，最大のもの｣に過ぎない．素数が無数に存在することはすでに分かっているため，厳密には｢最大の素数｣は存在しない．

ちなみに，以前まで｢最大｣の地位を保持していた素数は，2018年12月21日に発表された
\[ 2^{82589933}-1\]
であり，24862048桁の素数であったが，今回発見された素数はそれを大幅に上回る41024320桁である．

GIMPSは，無料で提供しているプログラムを用いて新たな素数を発見した場合，発見者に3000ドルの賞金を授与するとしている．

現在発見されている素数の大きさランキング

現在発見されている素数を大きい順に並べたとき，トップ10に入っているのは次の通り．

順位	素数	桁数	発見年月	発見者
1	$2^{136279841}-1$	41024320	2024年	Luke Durant
2	$2^{82589933}-1$	24862048	2018年	Patrick Laroche
3	$2^{77232917}-1$	23249425	2018年	Jonathan Pace
4	$2^{74207281}-1$	22338618	2016年	Curtis Cooper
5	$2^{57885161}-1$	17425170	2013年	Curtis Cooper
6	$2^{43112609}-1$	12978189	2008年	Edson Smith
7	$2^{42643801}-1$	12837064	2009年	Odd Magnar Strindmo
8	$516693^{2097152}-516693^{1048576}+1$	11981518	2023年	Ryan Propperら
9	$465859^{2097152}-465859^{1048576}+1$	11887192	2023年	Ryan Propperら
10	$2^{37156667}-1$	11185272	2008年	Hans-Michael Elvenich

2024年に見つかった素数

今回は｢過去最大の素数が見つかった｣ということで話題になったが，実は新しい素数が発見されるのは珍しいことではない．ここでは，2024年に発見された素数の中からいくつかを紹介しよう．

まず，2024年4月に発見された388342桁の双子素数である．執筆時点で，3番目に大きい双子素数である．
\[ 669821552^{16384}-669821552^{8192}\pm 1\]
双子素数とは，素数の組$(p,p+2)$のことである．

次に，2024年10月に発見された3395992桁の階乗素数である．執筆時点で，最も大きい階乗素数である．
\[ 632760!-1\]
階乗素数とは，正の整数$n$を用いて$n!\pm 1$の形で表される素数のことである．

そして，2024年8月に発見された2765105桁の素数階乗素数である．執筆時点で，最も大きい素数階乗素数である．
\[ 6369619\sharp +1\]
素数階乗素数とは，素数$p$を用いて$p\sharp \pm 1$の形で表される素数のことである．なお，$p\sharp$は$p$以下のすべての素数の積を表す．

さらに，2024年10月に発見された100391桁のソフィー･ジェルマン素数である．執筆時点で，3番目に大きいソフィー･ジェルマン素数である．
\[ 47356235323005 ·\times 2^{333443}-1\]
ソフィー･ジェルマン素数とは，$p,2p+1$がともに素数であるような$p$のことである．

最後は，2024年10月に発見された8238312桁の一般化フェルマー素数である．執筆時点で，14番目に大きい素数であり，最も大きい一般化フェルマー素数である．また，2024年10月までに発見された素数の中で，今回発見された素数に次いで，2番目に大きい素数である．
\[ 4\times 5^{11786358}+1=(2\times 5^{5893179})^{2^1}+1\]
一般化フェルマー素数とは，$3$以上の整数$a$，正の整数$n$を用いて$a^{2^n}+1$の形で表される素数のことである．

ここからは，より詳細な数学的背景を解説する．なお，重要な性質に焦点を絞っているため，厳密な議論や深入りはしていない．証明は読み飛ばしても構わない．

素数の定義

素数とは，次のように定義される数のことである．

定義1

$1$とその数自身のみを正の約数に持つ正の整数を素数という．ただし，$1$を除く．

端的に言えば，｢$1$とその数自身で割り切れ，それ以外では割り切れない数｣のことである．｢正の約数の個数が2つである正の整数｣と考えてもよい．具体例を見ていこう．

例1

$2$は素数である．実際，$2$は$1$と$2$のみで割り切れ，それ以外の正の整数では割り切れない．
$2024$は素数でない．実際，$2024$は$1,2,4,8,11,22,23,44,46,88,92,184,253,506,1012,2024$で割り切れる．
$1021$は素数である．実際，$1021$は$1$と$1021$のみで割り切れ，それ以外の正の整数では割り切れない．

$1$が素数でないことには注意が必要である．これは，$1$を素数とすると，素因数分解の一意性が成り立たなくなってしまうためとされているが，この記事では深入りしない．

素数が無数に存在することは，古代から知られている．最も有名な証明は，次のユークリッドによるものである．

定理1

素数は無数に存在する．

証明¹

$n$を正の整数とする．素数が$p_1,p_2,\dots ,p_n$の$n$個しかないと仮定すると，次の式で表される整数
\[ P=p_1p_2\dots p_n+1\]
は$p_1,p_2,\dots ,p_n$のいずれの素数でも割り切れない．よって，$P$は素数であり²，$p_1,p_2,\dots ,p_n$のいずれとも異なる．ゆえに，少なくとも$n+1$個の素数が存在することになり矛盾．
したがって，素数は無数に存在する．$\blacksquare$

定理1より，｢最大の素数｣は存在しないことが分かった．

素数は整数の約数に関する概念であるが，約数についての未解決問題はたくさんあり，現代数学の重要な分野の一つである．

メルセンヌ素数

メルセンヌ素数は，次のように定義される特殊な素数のことを指す．

定義2

$n$を正の整数とする．$2^n-1$の形で表される整数をメルセンヌ数といい，$M_n$で表す．素数であるメルセンヌ数をメルセンヌ素数という．

メルセンヌ素数は式の形がそこまで複雑なものではなく，便利な素数判定法が存在する．また，$2$の累乗の形を含むため，巨大な素数を得ることが比較的簡単である．そのため，現在発見されている具体的な素数を大きい順に並べると，メルセンヌ素数が上位を占めているのである．

さて，次の定理2を利用すると，メルセンヌ素数の探索の手間を減らすことができる．

定理2

$n$を正の整数とする．メルセンヌ数$M_n$が素数ならば，$n$は素数である．

定理2は，初等的に証明することができる．

証明

対偶｢$n$が素数でないならば，$M_n$は素数でない｣ことを示す．
$n=1$のとき，$M_1=1$は素数でない．
$n$が合成数のとき，$2$以上の整数$a,b$を用いて$n=ab$と表される．このとき
\[ M_n=M_{ab}=2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+\dots +2^{(b-1)a})\]
であり，$2^a-1,1+2^a+2^{2a}+\dots +2^{(b-1)a}$のいずれも$1$でないから，$M_n$は合成数である．
以上より，対偶が真であることが示されたから，元の命題も成り立つ．$\blacksquare$

よって，メルセンヌ素数を探索するときは，$p$を素数として，$M_p=2^p-1$の場合のみを調べればよい．

例2

$M_5=2^5-1=31$はメルセンヌ素数である．
$M_{11}=2^{11}-1=2047=23\times 89$はメルセンヌ素数でない．

調べるメルセンヌ数が限定されたとはいえ，$M_p$が素数であるかどうかを簡単に判定する方法があれば非常に便利である．

素数判定法

ここからは，非常に有用な素数判定法を紹介する．以下，$p$を素数とする．

リュカ-レーマー･テスト

メルセンヌ素数が巨大な素数の探索対象となっているのは，次のような判定法が確立されているからである．

定理3(リュカ･テスト)

$p\equiv 3\pmod{4}$のとき，数列$\{ S_n\}_{n=0}^{\infty}$を
\[ S_0=3,\qquad S_{n+1}=S_n^2-2\quad (n=0,1,2,\dots )\]
により定める．
このとき，$S_{p-2}$が$M_p$で割り切れることと，$M_p$が素数であることは同値である．

これを更に一般化したものがリュカ-レーマー･テストである．

定理4(リュカ-レーマー･テスト)

$p$が奇素数のとき，数列$\{ S_n\}_{n=0}^{\infty}$を
\[ S_0=4,\qquad S_{n+1}=S_n^2-2\quad (n=0,1,2,\dots )\]
により定める．
このとき，$S_{p-2}$が$M_p$で割り切れることと，$M_p$が素数であることは同値である．

定理4の証明は難しい．整数論や群論についての知識が必要となる．ここでは，その証明に用いる補題を証明しておく．

補題1

数列$\{ S_n\}_{n=0}^{\infty}$を
\[ S_0=4,\qquad S_{n+1}=S_n^2-2\quad (n=0,1,2,\dots )\]
により定めるとき
\[ S_n=(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}\qquad (n=0,1,2,\dots )\]

証明

$n$に関する数学的帰納法で示す．

$n=0$のとき
\[ (2+\sqrt{3})^{2^0}+(2-\sqrt{3})^{2^0}=4=S_0\]

$n=k$で与式が成り立つと仮定すると
\[ \begin{aligned}S_{k+1}&=((2+\sqrt{3})^{2^k}+(2-\sqrt{3})^{2^k})^2-2\\ &=((2+\sqrt{3})^{2^k})^2+2((2+\sqrt{3})(2-\sqrt{3}))^{2^k}+((2-\sqrt{3})^{2^k})^2-2\\ &=(2+\sqrt{3})^{2^{k+1}}+(2-\sqrt{3})^{2^{k+1}}\end{aligned}\]
よって，$n=k+1$のときも成り立つ．

したがって，示された．$\blacksquare$

数列の一般項を利用するため，合同式の定義を拡張する．

定義3

$a,b,c,d,n$を整数とする．$a\equiv c,b\equiv d\pmod{n}$のとき
\[ a+b\sqrt{3}\equiv c+d\sqrt{3}\pmod{n}\]
であると定める．

また，次の補題も重要である(フェルマーテストについても重要)．

補題2(フェルマーの小定理)

$p$を素数，$a$を$p$と互いに素な正の整数とするとき，次が成り立つ．
\[ a^{p-1}\equiv 1\pmod{p}\]

証明

まず，$a,2a,\dots (p-1)a$を$p$で割った余りはすべて異なることを示す．
$i,j$を$1$以上$p-1$以下の整数とする．$ia\equiv ja\mod{p}$と仮定すると，$(i-j)a$は$p$の倍数となる．$a$と$p$は互いに素であるから，$i-j$は$p$の倍数であり，$0\leqq |i-j|<p$より$i=j$である．よって，示された．

ゆえに，$a,2a,\dots (p-1)a$を$p$で割った余りは，小さい順に$1,2,\dots ,p-1$であるから
\[ a\cdot 2a\dots (p-1)a\equiv (p-1)!\pmod{p}\]
すなわち
\[ (p-1)!a^{p-1}\equiv (p-1)!\pmod{p}\]
$(p-1)!$と$p$は互いに素であるから，両辺を$(p-1)!$で割ると
\[ a^{p-1}\equiv 1\pmod{p}\]
が従う．$\blacksquare$

これらの補題を用いることで証明できる．詳しい証明は参考文献の6や16に掲載されている．

フェルマーテスト

リュカ-レーマー･テストでは，具体的なメルセンヌ数が素数であるかどうかを判定するためのアルゴリズムである．今回の素数の発見には，その前にフェルマーテストが行われた．フェルマーテストでは，素数の可能性があるかどうかを教えてくれるアルゴリズムである．

定理5

$n$が素数である可能性があるかどうかを，以下の試行を繰り返して検証する．

$a$を$2$以上$n-1$以下の整数の中からランダムに1つ固定する．
$a$と$n$が互いに素であるとき，$a^{n-1}\not\equiv 1\pmod{n}$ならば，フェルマーの小定理の対偶より$n$は素数でない．
$a$と$n$が互いに素でないとき，$a$と$n$の$1$でない正の公約数は$n$の因数であるから$n$は素数でない．

つまり，$a$と$n$が互いに素であり，$a^{n-1}\equiv 1\pmod{n}$が成り立つならば，｢$n$は素数でない｣と判定することはできないため，素数である可能性があるということが分かる．このとき，$n$は$a$を底とする確率的素数であるという．ここで重要なのは，$n$が合成数であっても，$a^{n-1}\equiv 1\pmod{n}$が成り立つ場合があるということである．このような$n$は$a$を底とするフェルマー擬素数と呼ばれている．

例3

$341$は$2$を底とするフェルマー擬素数である．実際，次の合同式
\[ 2^{340}\equiv 1\pmod{341}\]
が成立するが，$341=11\times 31$であり，$341$は素数でない．
$561$は，$561$と互いに素な$2$以上$560$以下の任意の整数$a$に対して，$a$を底とするフェルマー擬素数である．実際，次の合同式
\[ a^{560}\equiv 1\pmod{560}\]
が成立するが，$561=3\times 11\times 17$であり，$561$は素数ではない．

$561$のようなフェルマー擬素数はカーマイケル数と呼ばれている．

定義4

$3$以上の整数$n$と互いに素な$2$以上$n-1$以下の任意の整数$a$に対して，次の合同式
\[ a^{n-1}\equiv 1\pmod{n}\]
が成立するとき，$n$をカーマイケル数という．

実は，$561$は最小のカーマイケル数である．

いずれにせよ，カーマイケル数にフェルマーテストを実行すると，互いに素でない整数が選ばれない限り，合成数とは判断されないのである．この意味でも，フェルマー･テストは完璧な素数判定法とは言えない．

ちなみに，フェルマーテストを改善したアルゴリズムとして，ミラー-ラビン素数判定法やAKS素数判定法がある．

メルセンヌ素数の歴史

メルセンヌ素数が研究対象となる背景には，完全数の存在があった．

定義5

正の約数の総和が自身の$2$倍に等しい正の整数を完全数という．

具体例を見ていこう．

例4

$6$は完全数である．実際，$6$の正の約数は$1,2,3,6$であり，これらの総和は$12=2\times 6$である．
$28$は完全数である．実際，$28$の正の約数は$1,2,4,7,14,28$であり，これらの総和は$56=2\times 28$である．

数学者･天文学者のユークリッド(エウクレイデス)(Euclid, 紀元前3世紀頃)による著作『原論』には，次の定理とその証明が掲載されている．

定理6

$M_n$が素数ならば，$2^{n-1}M_n$は完全数である．

証明

$M_n$が素数ならば，$M_n=2^n-1$より$M_n\neq 2$であることに注意すると，$2^{n-1}M_n$は整数が素因数分解された形であると言える．このとき，正の約数の総和は
\[ (1+2+2^2+\dots +2^{n-1})(1+M_n)=1\cdot \frac{2^n-1}{2-1}\cdot (1+M_n)=(2^n-1)2^n=2\cdot 2^{n-1}M_n\]
であるから，$2^{n-1}M_n$は完全数である．$\blacksquare$

つまり，メルセンヌ素数が見つかれば，それに対応した完全数も見つけることができるのである．

さて，メルセンヌ素数の初期の研究では，定理2より，$p$を素数とすると，$M_p$のみを考えればよいことが分かった．それと同時に，$M_p$はすべて素数なのではないかと予想された．しかし，Hudalricus Regiusは$M_{11}$が合成数であることを示し，この予想が誤っていることが分かった．

その後，ピエトロ･カタルディ(Pietro Cataldi, 1548-1626)は$M_{17},M_{19}$が素数であることを示し，$M_{23},M_{29},M_{31},M_{37}$は素数であると予想したが，ピエール･ド･フェルマー(Pierre de Fermat, 1607-1665)は$M_{23}$と$M_{37}$が素数でないことを示した．

そして，メルセンヌ素数の名前の由来となった人物，マラン･メルセンヌ(Marin Mersenne, 1588-1648)が1644年に，著書”Cogitata Physica-Mathematica”の中で｢$M_p$が素数となるような素数$p\leqq 257$は，$2,3,5,7,13,17,19,31,67,127,257$のみである｣と予想した．この予想に対する最初の成果は，1738年にレオンハルト･オイラー(Leonhard Euler, 1707-1783)が$M_{29}$が素数でないことを示し，1772年に$M_{31}$が素数であることを示したものである．1876年には，リュカ･テストの考案者フランソワ・エドゥアール・アナトール・リュカ(François Édouard Anatole Lucas, 1842-1891)によって$M_{67}$が素数でないことと，$M_{127}$が素数であることが示された．リュカ･テストはその後改良され，Ivan Mikheevich Pervushin(1827-1900)が$M_{61}$，Ralph Ernest Powers(1875-1952)が$M_{89},M_{107}$といったメルセンヌの予想にない素数が見つかった．$M_{257}$について分かったのは，予想から278年後の1922年のことであり，素数でないことが分かった．

メルセンヌの予想は正しかったとは言えないが，この予想によってメルセンヌ素数の研究は飛躍的に進歩したことから，メルセンヌの名が残ることになった．

1903年には，フランク・ネルソン・コール(Frank Nelson Cole, 1861-1926)がアメリカ数学会の会議で
\[ M_{67}=193707721\times 761838257287\]
が等しいことを，無言で両辺を計算することによって証明した．$M_{67}$が合成数であることはリュカによって分かっていたが，具体的にどのように素因数分解できるかは分かっていなかったのである．

メルセンヌ素数の探求は，コンピュータの登場によって急速に発展した．

1952年，Raphael Mitchel Robinson(1911-1995)がSWACと呼ばれるコンピュータを用いて$M_{521},M_{607},M_{1279},M_{2203},M_{2281}$の5つのメルセンヌ素数が発見された．初めてコンピュータによってメルセンヌ素数が見つかった瞬間である．

1996年にはメルセンヌ素数の発見を目的とした分散コンピューティングGIMPS(Great Internet Mersenne Prime Search)が発足し，35番目のメルセンヌ素数$M_{1398269}$以降のすべてのメルセンヌ素数の発見に，GIMPSが関与している(執筆現在)．

2008年には初めて1000万桁を超える素数$M_{42623801}$が発見され，電子フロンティア財団による賞金10万ドルが贈られた．

そして2024年10月，通算52個目となるメルセンヌ素数$M_{136279841}$が発見され，過去最大の既知の素数が更新された．

メルセンヌ素数の一覧

現在，メルセンヌ素数は$52$個発見されており，順番が確定しているものが$48$個ある．メルセンヌ素数が無数に存在するかどうかは分かっていないため(詳細は後述)，これ以外のメルセンヌ素数が存在するかどうかも不明である(執筆現在)．

番号(小さい順)	$p$	$M_p$の桁数
1	2	1
2	3	1
3	5	2
4	7	3
5	13	4
6	17	6
7	19	6
8	31	10
9	61	19
10	89	27
11	107	33
12	127	39
13	521	157
14	607	183
15	1279	386
16	2203	664
17	2281	687
18	3217	969
19	4253	1281
20	4423	1332
21	9689	2917
22	9941	2993
23	11213	3376
24	19937	6002
25	21701	6533
26	23209	6987
27	44497	13395
28	86243	25962
29	110503	33265
30	132049	39751
31	216091	65050
32	756839	227832
33	859433	258716
34	1257787	378632
35	1398269	420921
36	2976221	895932
37	3021377	909256
38	6972593	2098960
39	13466917	4053946
40	20996011	6320430
41	24036583	7235733
42	25964951	7816230
43	30402457	9152052
44	32582657	9808358
45	37156667	11185272
46	42643801	12837064
47	43112609	12978189
48	57885161	17425170
49?	74207281	22338618
50?	77232917	23249425
51?	82589933	24862048
52?	136279841	41024320