# Fermat primes relation to $2^n+1$

If $2^n+1$ is prime how to show that $n$ must be a power of $2$

Being at elementary level I am at a loss what to begin with?

• You mean $2^n+1$. Where to begin: proof by contradiction. Hint: $(x+1)\mid(x^k+1)$ for odd $k$. This question has many many duplicates. One of them is on the list of "Related" links off to the right. – anon Sep 12 '13 at 17:30

Suppose that $n$ is odd. Then $$x^n=(x+1-1)^n=(-1)^n= -1\mod x+1$$ so that $x+1\mid x^n+1$. Thus if $2^n+1$ is not composite, it must be the case $n=2^u$. If you want to be explicit \begin{align} \frac{{{x^n} + 1}}{{x + 1}} &= \frac{{{{( - x)}^n} - 1}}{{( - x) - 1}} \cr &= \frac{{{u^n} - 1}}{{u - 1}} \cr &= 1 + u + {u^2} + \cdots + {u^{n - 1}} \cr &= 1 - x + {x^2} - + \cdots + {\left( { - 1} \right)^{n - 1}}{x^{n - 1}} \end{align}