Mersenne Prime Exponent Cannot Be Even

In this problem we explore a classic property of Mersenne primes: if $2^n-1$ is prime, then $n$ must be odd—in fact, prime. This is a great exercise in proof by contrapositive and algebraic factorisation, techniques that appear frequently in the HSC Mathematics Extension 1 course. By working through the solution, you'll see how a simple difference-of-squares factorisation can transform a statement about primality into an argument about composite numbers.

Problem Statement

Prove that for all integers $n \geq 3$, if $2^n - 1$ is prime, then $n$ cannot be even.

---

Hints

Use proof by contrapositive. Instead of proving "$P \implies Q$", prove "$\neg Q \implies \neg P$".

That is, prove: "If $n$ is even (and $n \geq 3$), then $2^n - 1$ is composite."

Write $n = 2k$ and factor $2^{2k} - 1$ as a difference of squares.

---

Solutions

Proof by Contrapositive:

We prove the contrapositive: If $n$ is even (with $n \geq 3$), then $2^n - 1$ is composite.

Assume $n$ is even. Then $n = 2k$ for some integer $k$.

Since $n \geq 3$ and $n$ is even, we have $n \geq 4$, so $k \geq 2$.

Now, $2^n - 1$ becomes $2^{2k} - 1$. Using the index law $2^{2k} = (2^k)^2$, we can rewrite the expression as a difference of two squares:

$$2^n - 1 = 2^{2k} - 1 = (2^k)^2 - 1^2$$

Factor as difference of squares:

$$2^n - 1 = (2^k - 1)(2^k + 1)$$

Since $k \geq 2$:

• $2^k \geq 4$, so $2^k - 1 \geq 3 > 1$
• $2^k \geq 4$, so $2^k + 1 \geq 5 > 1$

Both factors are integers strictly greater than $1$, so their product is composite.

Therefore, $2^n - 1$ is composite.

By contrapositive, if $2^n - 1$ is prime, then $n$ cannot be even. $\blacksquare$

Note: This is why Mersenne primes have the form $2^p - 1$ where $p$ itself is prime (though not all such numbers are prime).

---

Takeaways

• Reconstruct the full proof from the hint and the solution outline, and justify every transformation explicitly.
• Check edge cases and verify where each assumption is used in the argument.

---

Further Readings

If you found this proof interesting, be sure to check out these relevant HSC booklets to sharpen your reasoning skills: HSC Proofs, HSC Polynomials, HSC Trigonometry