# 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 49 known mersenne primes to date, though we hope that it will change in the future. An interesting thing about Mersenne primes is that they are the easiest to prove to be primes, so they are the largest 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 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 a perfect number can be written of the form \(2^{n-1}(2^{n}-1)\), and if the term \(2^{n}-1\) is a prime number then it 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 perfect number!

## 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.

Read the following statements carefully:

\([1]\). For all prime numbers \(p\), \(2^p-1\) is a prime number.

\([2]\). If \(p\) is a composite number, then it is impossible for \(2^p-1\) to be a prime number.

\([3]\). Statement number \([1]\) isn't true.

Which of these statements is/are correct?

## Lucas–Lehmer Primality Test

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,

\(\begin{align} 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}. \end{align}\)

Since \(k-2=9\) and \(a_9 \equiv 0 \pmod{2^k-1} \) is false.

Therefore, \({ 2 }^{ 11 }-1\) is not prime. \(_\square\)

## The Largest Known Prime Number

There are \(49\) known Mersenne primes, with the largest known prime being \[ \large 2^{74,207,281} - 1,\] which is over 22 million digits long!

This enormous number was discovered by Curtis Cooper at the University of Central Missouri, Warrensburg, 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 22,338,618 digits in total.

## Exercises for the Reader

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