Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A little bird told me that if $2^n+1$ is prime, then $n$ is a power of $2$. I tend not to trust talking birds, so I'm trying to verify that statement independently.

Suppose $n$ is not a power of $2$. Then $n = a \cdot 2^m$ for some $a$ not a power of $2$ and some integer $m$. This gives $2^n+1 = 2^{a \cdot 2^m}+1$. Now I suspect there's a way to factor that, but I don't see how. Can someone give me a hint?

share|cite|improve this question
A proof of this fact is also given in Wikipedia article on Fermat primes. – Martin Sleziak May 4 '12 at 10:06
Neat. I didn't know it had a name. – Rob May 4 '12 at 10:10
Disproof: $2^0+1=2$ → $n=2^k=0$? – xoxox Feb 18 at 17:47
up vote 14 down vote accepted

Hint. For any odd natural number $a$, the polynomial $x+1$ divides $x^a+1$ evenly.

In particular, we have $$ \frac{x^a+1}{x+1}=\frac{(-x)^a-1}{(-x)-1}=1-x+x^2-\cdots+ (-x)^{a-1}$$ by the geometric sum formula. In this case, specialize to $x=2^{2^{\large m}}$ and we have a nontrivial divisor. (Also, $x^a+1\equiv(-1)^a+1\equiv-1+1\equiv0\mod x+1$ inside $\Bbb Z[ x]$ is pretty slick.)

share|cite|improve this answer
Hi, sorry for a late post, but could you explain your answer a bit more for me. Did you mean to say, set $x = 2^m$ instead of $x = 2^{2^m}$ – Tyler Hilton Jan 28 '13 at 8:01
@TylerHilton No, I meant $x=2^{2^m}$ as I wrote. If $n=a2^m$ with $a$ odd, then this shows that $2^{2^m}+1$ divides $2^{a2^m}+1=2^n+1$, and hence $2^n+1$ is composite when $n$ is not a power of $2$. – anon Jan 28 '13 at 8:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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