# If 2n+12^n+1 is prime, why must nn be a power of 22?

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?

Hint. For any odd natural number $$aa$$, the polynomial $$x+1x+1$$ divides $$xa+1x^a+1$$ evenly.
In particular, we have $$xa+1x+1=(−x)a−1(−x)−1=1−x+x2−⋯+(−x)a−1 \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=22mx=2^{2^{\large m}}$$ and we have a nontrivial divisor.
(Also, $$x^a+1\equiv(-1)^a+1\equiv-1+1\equiv0\mod x+1x^a+1\equiv(-1)^a+1\equiv-1+1\equiv0\mod x+1$$ inside $$\Bbb Z[ x]\Bbb Z[ x]$$ is pretty slick.)