📂Number Theory

Mersenne Primes

Definition ¹

If $M_{n} = 2^{n} - 1$ is a prime number, $M_{n}$ is called a Mersenne Prime.

Explanation

The discovery of Mersenne primes begins with the exploration of whether $p=x^{n}-1$ is a prime number. One immediately realizes that if $x$ is odd, except for $p=2$, it cannot be a prime. Also, since $$x^{n}-1 = (x-1) ( x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 )$$, no matter what number $( x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 )$ is, at least $(x-1)$ must be specifically $1$ to be considered a prime. That means $x$ must be not just even but precisely $2$, and hence we only need to concern ourselves with forms of $p= 2^{n} - 1$.

As of May 2018, there have been a total of $50$ Mersenne primes discovered, with the largest being $M_{77,232,917}$. This number is significant, reaching up to $23,249,425$ digits. Meanwhile, examining the first few Mersenne primes reveals some interesting points.

$$\begin{align*} M_{2} &= 2^{2} - 1 = 3 \\ M_{3} &= 2^{3} - 1 = 7 \\ M_{5} &= 2^{5} - 1 = 31 \\ M_{7} &= 2^{7} - 1 = 127 \\ M_{13} &= 2^{13} - 1 = 8191 \end{align*}$$

Theorem

For the Mersenne prime $M_{n}$, $n$ is prime.

Proof

For the Mersenne prime $M_{n} = 2^{n} - 1$, if we assume two integers $a,b$, such that $n=ab$, then $$2^{ab} - 1 = (2^{a} - 1) ( 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^{a} + 1 )$$ That is, $2^{ab} - 1$ would be a composite number, which contradicts the assumption.

■

A counterexample that shows the converse is not true is when $n=11$. $M_{11} : = 2^{11} - 1 = 2047$ is the product of $23$ and $89$, where $M_{11}$ is not a Mersenne prime.