# $2^n + 1$ is prime $\implies n$ is a power of $2$

I was wondering why I can't do this this way by proof by contradiction of the contrapositive. So I want to prove
$$2^n + 1 \quad \text{is prime} \implies n = 2^k \quad \text{for some} \ k\in \mathbb{Z}.$$
By contrapositive,
$$n \neq 2^k \quad \text{for all} \ k \in \mathbb{Z} \implies 2^n + 1 \quad \text{is composite.}$$

Then I want to prove by contradiction:
Suppose $n \neq 2^k \quad \forall k\in \mathbb{Z}$ and $2^n + 1$ is prime.
Why can't I give one counterexample to prove that this is false (contradiction)?
Since if $n:= 3$ then $2^3 + 1 = 9$ which is composite, hence, $2^n + 1$ being prime (hypothesis) cannot be true, so by proof by contradiction, $2^n +1$ must be composite?

• Because you have to prove it for all $k \in \mathbb{Z}$. – Math Lover Aug 15 '17 at 4:18
• Strictly speaking you also need $n\gt 0$, because $2^0 + 1 = 2$ is prime (but $0$ is not a power of $2$). – hardmath Aug 15 '17 at 4:33
• You want to "prove" that All Nordic women have blonde hair by exhibiting a Chinese lady with black hair? – Jyrki Lahtonen Aug 15 '17 at 4:45
• @Math Lover I think it should be for all $k\in\mathbb N$. – Michael Rozenberg Aug 15 '17 at 4:53
• Possible duplicate of Fermat primes relation to $2^n+1$ – Gerry Myerson Aug 19 '17 at 22:26

## 2 Answers

The question isn't to show that there is one $n$ that is not a power of $2$ with $2^n+1$ composite, it is to show that for every $n$ that is not a power of $2$, $2^n+1$ is composite.

• I see; would my contrapositive and then contradiction (or just contrapositive) path lead to anything? – OneGapLater Aug 15 '17 at 4:20
• Yes, that is indeed the typical route to go about proving this statement. – Ziryerx Aug 15 '17 at 5:47

Suppose there is a odd prime $p|n$. Then $n=p\cdot k$ for some natural $k$. Now we have: $$2^{pk}+1 =(2^k+1)(2^{k(p-1)}-2^{k(p-2)}+...-2^k+1)$$

Clearly both factors are > 1 and thus a contradction.