Proof that if 2^n − 1 is prime then n is prime

Proof

We prove the contrapositive: if $n$ is not prime, then $2^n - 1$ is not prime.

1. Let $n$ be a natural number that is not a prime number. Then $n = 0$, $n = 1$, or $n$ is composite.
2. If $n = 0$, then $2^n - 1 = 0$. If $n = 1$, then $2^n - 1 = 1$. Neither $0$ nor $1$ is prime.
3. Let $n$ be composite. Then $n = ab$ with integers $a$ and $b$ such that $1 < a < n$ and $1 < b < n$.
4. For every number $x$ and every integer $b \ge 1$, $(x - 1)(1 + x + x^2 + \dots + x^{b-1}) = x^b - 1$. Indeed, the product telescopes: $\sum_{i=0}^{b-1} (x^{i+1} - x^i) = x^b - 1$.
5. Put $x = 2^a$. Then $2^n - 1 = x^b - 1 = (2^a - 1) \cdot s$, where $s = 1 + 2^a + \dots + 2^{a(b-1)}$ is a positive integer.
6. So $2^a - 1$ divides $2^n - 1$.
7. Since $1 < a < n$, we have $1 < 2^2 - 1 \le 2^a - 1 < 2^n - 1$.
8. So $2^n - 1$ has a divisor strictly between $1$ and itself, and it is not prime.
9. By contraposition, if $2^n - 1$ is prime, then $n$ is prime.