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.

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 = a b$ 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 = a b$ . We have a polynomial factorization:

$x^{n} - 1 = x^{a b} - 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.