メルセンヌ数(メルセンヌすう、英: Mersenne number)とは、2の冪よりも 1 小さい自然数、すなわち 2n − 1(n は自然数)の形の自然数のことである。これを Mn で表すことが多い。メルセンヌ数を小さい順に列挙すると1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, ... (オンライン整数列大辞典の数列 A000225
)となる。メルセンヌ数は2進法表記で n 桁の 11?11、すなわちレピュニットとなる。
Mn = 2n − 1 が素数ならば n もまた素数であるが、逆は成立しない (M11 = 2047 = 23 × 89)。素数であるメルセンヌ数をメルセンヌ素数(メルセンヌそすう、英: Mersenne prime)という。なお、「メルセンヌ数」という語で、n が素数であるもののみを指したり[1]、さらに狭義の意味でメルセンヌ素数を指す場合もある[注釈 1]。 Mn が素数ならば n もまた素数であることは、次の式から分かる[2][3]:2ab − 1 = (2a − 1)(1 + 2a + 22a + ? + 2(b−1)a). 対偶命題「n が合成数ならば Mn は合成数である」が示される。また、この等式より、m 。n のとき Mm 。Mn である。一方、 p が素数でも Mp が素数とは限らない。最小の反例は p = 11 の場合であり、M11 = 2047 = 23 × 89 が成り立つ。 (奇)素数 p に対して Mp が素数であるかどうかは、リュカ-レーマー・テストによって判定できる (#素数判定法節を参照)。 Mp = 2p − 1 が素数ならば、2p−1(2p − 1) は完全数である[2][4]。この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた[5]。したがって、完全数の探索はメルセンヌ素数の探索に終始された。 2p−1(2p − 1) は明らかに偶数であるが、偶数の完全数でこの生成式から得られるもの以外はないのか2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された[4]。 p を素数とする。 メルセンヌ素数(メルセンヌそすう、Mersenne prime)とは、素数であるメルセンヌ数のことである。 2022年2月現在知られている最大のメルセンヌ素数は、2018年12月に発見された、それまでに分かっている中で51番目のメルセンヌ素数 282589933 − 1 であり、十進法で表記したときの桁数は2486万2048桁に及ぶ[GIMPS 1]。 メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2n − 1 が素数ならば、2n − 1(2n − 1) は完全数である」ことを証明した[9]。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる[10][注釈 2]。 小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている[11][12]。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルース (fr:Ibn Fallus
基本的な性質
完全数
メルセンヌ数の素因数
Mp の素因数は 2p を法として 1 と合同[6]、かつ 8 を法として 1 または −1 と合同である[7]。
p ≡ 3 (mod 4) のとき、Mp が 2p + 1 で割れることと、2p + 1 が素数であることは同値である[7]。
ある計算可能な正定数 c が存在して、Mp の最大素因数を q について、q ? cp log p [8]。
メルセンヌ素数
メルセンヌ素数の発見の歴史
古代?中世
メルセンヌの予想
Size:72 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)』
担当:undef