Mersenne Prime

A Mersenne prime is a prime number that can be written in the form $2^{n}-1$. For example $31$ is a Mersenne prime that can be written as $2^{5}-1$. The first few Mersenne primes are $3, 7, 31, 127, 8191$. There are 50 known Mersenne primes as of June 2018, though we hope that it will change in the future. An interesting thing about Mersenne primes is that they are the easiest natural numbers to prove to be primes, so they make up the largest category on the list of known prime numbers.

The search and curiosity for Mersenne primes came from the study of perfect numbers. A perfect number is a number that can be written as the sum of its positive proper divisors. For example, $6$ is a perfect number as it can be written as $6=1+2+3$, and in fact it is the smallest perfect number. The next perfect number is $28=1+2+4+7+14$.

It can be shown that if a positive integer $a$ can be written in the form $2^{n-1}(2^{n}-1)$, such that $2^{n}-1$ is a prime number, then $a$ must be an even perfect number. We have seen that if $2^{n}-1$ is a prime number, then it is a Mersenne prime, which creates a one-to-one correspondence between Mersenne primes and even perfect numbers. That is, every Mersenne prime corresponds to exactly one even perfect number! (So far no odd perfect number has been found.)

Prove that if $2^{n}-1$ is prime, then $n$ must also be prime.

---

Let $p$ and $q$ be positive integers greater than one such that $n=p\cdot q$. Then using the factorization identity,

$${ 2 }^{ pq }-1=\left( { 2 }^{ p }-1 \right) \cdot \left( 1+{ 2 }^{ p }+{ 2 }^{ 2p }+{ 2 }^{ 3p }+\cdots+{ 2 }^{ p(q-1) } \right).$$

So if $n$ is composite and WLOG $1<p<q$, then we have the $2^{n}-1$ term to be composite because it is divisible by the $2^{p}-1$ term. $_\square$

The proof tells us that if $2^{n}-1$ is prime, then $n$ is also prime. But it doesn't guarantee that if $n$ is prime, then $2^{n}-1$ is prime, as we have not considered the second term in the above equation. A typical example of this is $11:$ even though it is a prime number, $2^{11}-1=2047$ isn't a prime number.

Lucas–Lehmer primality test is a primality test (an algorithm for determining whether an input number is prime) for Mersenne primes. It's currently known to be the most efficient test for Mersenne primes.

First we start with $n=0$.
Then ${ a }_{ n }={ a }_{ n-1 }^{ 2 }-2$ and ${ a }_{ 0 }=4.$
If you want to test if ${ 2 }^{ k }-1$ is prime, you have to check if ${ a }_{ k-2 }\equiv 0 ~\big( \text{mod }~ 2^k-1 \big)$ is true.

Prove that ${ 2 }^{ 11 }-1$ is not prime.

---

We could just find if there are other factors in that number, or we can use the Lucas–Lehmer primality test.

For this, $k=11$ and ${ 2 }^{ 11 }-1=2047.$ So,

• $a_0=4 \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=\big(194^2-2\big) \pmod{2047} =788 \pmod{2047}$
• $a_4=\big(788^2-2\big) \pmod{2047} =701 \pmod{2047}$
• $a_5=\big(701^2-2\big) \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=\big(240^2-2\big) \pmod{2047} =282 \pmod{2047}$
• $a_9=\big(282^2-2\big) \pmod{2047} =1736 \pmod{2047}.$

Since $k-2=9$ and $a_9 \equiv 0 \pmod{2^k-1}$ is false. Therefore, ${ 2 }^{ 11 }-1$ is not prime. $_\square$

There are $51$ known Mersenne primes, with the largest known prime being

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

which is over 24 million digits long!

This enormous number was discovered by Patrick Laroche in 2018, as part of the GIMPS (Great Internet Mersenne Prime Search). It is a collaborative effort to find new primes by pooling computing power online. It has 24,862,048 digits in total.

$\bullet$ Knowing that $p=23$ is prime, is it true that $M_{23} = 2^{23} - 1$ is prime?