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.