If $n$ is an even integer greater than $2$, then $2^n - 1$ is not a prime.

Question

Fairly new to Discrete Mathematics and I'm stumped on this one. So we're asked to prove:

If $n$ is an even integer greater than 2, then $2^n - 1$ is not a prime.

What I can come up with is that since $n > 2$, we know that $n$ is not prime since the only even $n$ happens to be $2$. We can write $n = 2k$ and so we rewrite $$2^n - 1 = 2^{2k}-1 = (2^k)^2 - 1 = (2^k-1)(2^k+1)$$

Up to here, am I even remotely correct? I'm not sure what else to say to take it from here to fully prove this. I also apologize for how I worded it, as I'm still trying to understand how to explain my proofs.

Answer 1

You are doing fine. Now that you have shown a factorization of $2^n-1$ the only thing that can go wrong is that one of the factors is $1$. So if $n \gt 2, \ldots$

A more general statement is that if $n$ is composite, $2^n-1$ is never prime. The reasoning is the same. If $n=ab$ with $a,b \gt 1$ then $2^n-1$ is divisible by $2^a-1$ and $2^b-1$. You can just do the division or search this site for the proof. Your problem is the $a=2$ case of this.

Answer 2

General advice: if you have a statement of the problem, make sure that you used all the points of the statement. Specificially, in this problem you should ask yourself a question: where did you used that $n>2$? Why your proof doesn't work for $n=2$? Then you'll see that to complete the proof you should in fact say why both $2^k-1$ and $2^k+1$ are not equal to $1$.

Also note that $2^{2k}-1$ is always divisible by $3$, this is another way to approach this problem.