Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

1 Answer

up vote 9 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|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
add comment

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.