Mersenne number is prime implies number is prime

Statement

Suppose $n$ is a positive integer such that the Mersenne number

$M_{n}=2^{n}-1$

is a prime number. Then $n$ itself is a prime number.

Related facts

• Mersenne number for prime or Poulet implies prime or Poulet

Proof

We prove the statement in its contrapositive form: if $n$ is not prime, then $M_{n}$ is not prime. The case $n=1$ is immediate, so we consider the case $n>1$, whereby it must be composite.

Given: $n=ab$ where $a,b$ are (possibly equal, possibly distinct) positive integers greater than 1.

To prove: $M_{n}=2^{n}-1$ is composite.

Proof: Write $n=ab$. We have a polynomial factorization:

$x^{n}-1=x^{ab}-1=(x^{a})^{b}-1=(x^{a}-1)(x^{a(b-1)}+x^{a(b-2)}+\dots +1)$

Plug in $x=2$ and get:

$2^{n}-1=(2^{a}-1)(2^{a(b-1)}+x^{a(b-2)}+\dots +1)$

Since $a,b$ are both greater than 1, $2^{a}-1$ and the other factor are both greater than 1, so $2^{n}-1$ is composite.