Showing $2^n -1$ is not prime for $n > 2$ where $n$ is even

I'm asked to prove that $2^n -1$ is not a prime number if $n$ is even and $n > 2$. Frankly, I don't know where to begin. So, how should I start tackling this question ?

Solution 1:

Proof 1: Factorising.

Let $n$ be even. Then $n = 2k$ for some $k \in \mathbb{N}$. Hence $2^n-1 = 2^{2k}-1 = (2^k-1)(2^k+1)$. The edge case is $n = 4$ (as this is the smallest even integer greater than 2), but clearly this is not a problem as $2^2-1 = 3$, so $2^n-1$ will always be composite for the specified $n$s.

Proof 2: Induction to show that $2^{2k}-1$ is divisible by 3 for all $k>1$.

Base case is trivial.

Let $m\in\mathbb{N}$, and suppose $3$ divides $2^{2m}-1$. Then $2^{2(m+1)}-1 = 2^{2m+2}-1 = 4\cdot2^{2m}-1 = 3\cdot2^{2m}+2^{2m}-1$. Hence $3$ divides $2^{2(m+1)}-1$, as required.

Solution 2:

The standard way to solve this problem, and what you're probably expected to do, is algebraic rewriting of $2^n - 1$, which the other answers will expound in full detail.

But if you have spent any time at all studying the $3x + 1$ conjecture, a slightly different, and perhaps more entertaining, approach suggests itself. $x$ is an integer, if it's even, you halve it, but if it's odd, you multiply it by 3 and add 1.

Lothar Collatz and others believe, but have not been able to prove, that if you iterate this function starting from any positive integer, that you will eventually reach 1, e.g., starting from 12 you get 12, 6, 3, 10, 5, 16, 8, 4, 2, 1.

Obviously if your iteration reaches a power of 2, the rest of the iteration is a downward listing of powers of 2 plunging all the way down to 1.

And, as it turns out, if $n$ is odd, then $2^n$ is reachable only from a halving step, e.g., half 16 is 8. But if $n$ is even, then $2^n$ is reachable either from a halving step or a thrice plus one step, e.g., $64 = 3 \times 21 + 1$.

That's because $2 \equiv 2 \pmod 3$ and $2^2 \equiv 1 \pmod 3$. Since $2 \times 1 = 2$, it follows that $2^n \equiv 2, 1, 2, 1, 2, 1, 2, 1, 2, \ldots \pmod 3$. So if $n$ is even, $$\frac{2^n - 1}{3}$$ is an integer, and more importantly for Collatz, an odd integer.

Therefore, to answer your question, if $x$ is a positive integer, the only way, $3x$ can be a prime number, is if $x = 1$, which corresponds to the $n = 2$ case of your question.