📂Number Theory

Mersenne Prime

Definition ¹

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

Explanation

The discovery of Mersenne primes begins with an inquiry into whether a number of the form $p=x^{n}-1$ is prime. What can be recognized at a glance from the expression is that if $x$ is odd, then it cannot be prime except for $p=2$. Moreover, 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 )$ turns out to be, at least $(x-1)$ must necessarily be $1$ for it to be prime. In other words, $x$ must not merely be even but exactly $2$, and therefore we only need to concern ourselves with the form $p= 2^{n} - 1$.

The number of Mersenne primes discovered up to May 2018 is $50$ in total, and the largest Mersenne prime is $M_{77,232,917}$. This is a large number whose number of digits alone reaches $23,249,425$. Meanwhile, if we examine the first few Mersenne primes that appear, we can find something interesting.

$$ \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 a Mersenne prime $M_{n}$, $n$ is prime.

Proof

For a Mersenne prime $M_{n} = 2^{n} - 1$, suppose that $n=ab$ for two integers $a,b$ that are not $1$. Then $$ 2^{ab} - 1 = (2^{a} - 1) ( 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^{a} + 1 ) $$ that is, $2^{ab} - 1$ is a composite number, which contradicts the assumption.

■

A counterexample showing that the converse does not hold is the case $n=11$. $M_{11} : = 2^{11} - 1 = 2047$ is the product of $23$ and $89$, so $M_{11}$ is not a Mersenne prime.