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?

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

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.

  • $\begingroup$ I see; would my contrapositive and then contradiction (or just contrapositive) path lead to anything? $\endgroup$ – OneGapLater Aug 15 '17 at 4:20
  • $\begingroup$ Yes, that is indeed the typical route to go about proving this statement. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.