梅森素数

一个梅森素数质数是否可以写成这种形式 $2 ^ {n} 1$．例如 $31$是一个梅森质数，可以写成 $2 ^ {5} 1$．前几个梅森质数是 $3,7,31,127, 8191$．截至2018年6月，已知的梅森质数有50个，不过我们希望未来能有所改变。关于梅森质数的一个有趣的现象是，它们是最容易被证明为质数的自然数，所以它们构成了已知质数列表中最大的一类。

对梅森质数的探索和好奇来自于<一个href="//www.parkandroid.com/wiki/perfect-numbers/" class="wiki_link" title="完美的数字" target="_blank">完美的数字．完全数是一个数，它可以被写成它的正固有因数的和。例如, $6$一个完全数是否可以写成这样 $6 = 1 + 2 + 3$，实际上它是最小的完全数。下一个完美数字是 $28日= 1 + 2 + 4 + 7 + 14$．

可以证明，如果一个正整数 $一个$可以写在表格里吗 $2 ^ {n} (2 ^ {n} 1)$,这样 $2 ^ {n} 1$是质数吗 $一个$一定是个偶数。我们已经看到了 $2 ^ {n} 1$是一个质数，那么它就是一个梅森质数，它在梅森质数和甚至完全数之间建立了一对一的对应关系。也就是说，每个梅森质数都对应一个偶数完全数!(到目前为止，还没有发现奇数完全数。)

证明,如果 $2 ^ {n} 1$是',那么 $n$也必须是质数。

---

让 $p$而且 $问$是大于1的正整数 $n = p \ cdot$．然后利用因式分解恒等式，

${2} ^ {pq} 1 = \离开({2}^ {p} 1 \) \ cdot \离开(1 + {2}^ {p} + {2} ^ {2 p} + {2} ^ {3 p} + \ cdots + {2} ^ {p (q1)} \右)。$

因此,如果 $n$是复合和WLOG $1 < p <问$，然后是 $2 ^ {n} 1$一项是合数因为它能被整除 $2 ^ {p} 1$术语。 $_ \广场$

证明告诉我们如果 $2 ^ {n} 1$是',那么 $n$也'。但它不能保证如果 $n$是',那么 $2 ^ {n} 1$是质数，因为我们没有考虑上面方程中的第二项。一个典型的例子是 $11：$尽管它是质数， $2 ^ {11} 1 = 2047$不是质数。

Lucas-Lehmer素数检验是一种针对梅森素数的素数检验(一种判断输入数是否是素数的算法)。这是目前已知的最有效的梅森质数检验方法。

首先我们从 $n = 0$．
然后 ${a}_{n}={a}_{n-1}^{2}-2$而且 ${a}_{0}=4。$
如果你想测试 ${2}^{k}-1$是质数，你要检查是否 ${一}_ {k-2} \枚0 ~ \大文本(\ {mod} ~ 2 ^ k - 1 \大)$是真的。

证明 ${2}^{11}-1$不是质数。

---

我们可以看看这个数中是否还有其他因子，或者我们可以用Lucas-Lehmer素数检验。

为此, $k = 11$而且 ${2}^{11}-1=2047。$所以,

• $= 4, a_0 \ pmod {2047}$
• $A_1 =\big(4^2-2\big) \pmod{2047} =14 \pmod{2047}$
• $A_2 =\big(14^2-2\big) \pmod{2047} =194 \pmod{2047}$
• $a_3 = \大(194大)^ 2 - 2 \ \ pmod {2047} = 788 \ pmod {2047}$
• $a_4 = \大(788大)^ 2 - 2 \ \ pmod {2047} = 701 \ pmod {2047}$
• $a_5 = \大(701大)^ 2 - 2 \ \ pmod {2047} = 119 \ pmod {2047}$
• $A_6 =\big(119^2-2\big) \pmod{2047} =1877 \pmod{2047}$
• $A_7 =\big(1877^2-2\big) \pmod{2047} =240 \pmod{2047}$
• $a_8 = \大(240大)^ 2 - 2 \ \ pmod {2047} = 282 \ pmod {2047}$
• $a_9 = \大(282大)^ 2 - 2 \ \ pmod {2047} = 1736 \ pmod{2047}。$

自 $k-2 = 9$而且 $A_9 \equiv 0 \pmod{2^k-1}$是假的。因此, ${2}^{11}-1$不是质数。 $_ \广场$

有 $51$已知的梅森质数，已知的最大质数是

$\large 2^{82,589,933} - 1，$

它的长度超过2400万位数!

这个巨大的数字是由帕特里克·拉罗彻在2018年发现的，作为gimp(伟大的互联网梅森素数搜索)。这是一项通过汇集在线计算能力来寻找新质数的合作努力。它总共有24862048位数字。

$\子弹$知道 $p = 23$是质数，对吗 $M_{23} = 2^{23} - 1$是质数吗?