When $n$ is odd, the relation $x^{n}+1 = (1+x)(1-x+x^{2}-\ldots+x^{n-1})$ yields \[\forall x \in \mathbb{N}, \forall n \in \mathbb{N}, n \text{ odd}, \ \ (x+1)|(x^{n}+1). \ \ \ (*)\] If $n$ is not a power of $2, n$ has at least one odd factor $p > 1.$ Let us write $n=pq$ with $q \in \mathbb{N}.$ The integer $2^{n}+1 = (2^{q})^{p}+1$ is divisible by $(2^{q}+1)$ thanks to $(*),$ hence composite. Therefore, $n$ has to be a power of $2.$

This problem is the key idea of the IMOSL'98 problem 18. If $n$ is not a power of two, then $n$ has an odd divisor $d$, thus $2^d+1|2^n+1$. But $2^d+1\equiv (-1)^d+1\equiv 0\pmod{3}$ thus $3|2^n+1$, and since $2^n+1$ is prime, it yields $n=1$, which is also a power of two. Thus the only odd divisor of $n$ must be 1. $\blacksquare$

teps wrote: This problem is the key idea of the IMOSL'98 problem 18. I pretty much doubt that ... what is the precise statement? Nobody notices this was known to Fermat (and is trivial)? The only primes of the form $2^n + 1$ may be those for which $n = 2^k$, and Fermat's wrong conjecture about the primality of all such ... Next we'll be asked to show that $2^n - 1$ may be a prime only if $n$ itself is a prime, and re-discover the Mersenne primes ...

http://www.artofproblemsolving.com/Forum/viewtopic.php?p=124436&sid=213d0011d81dded9c89c4af727272b9a#p124436 Well it was the first problem, which has a similar idea employed, to cross my mind. It isn't a key idea per se, but it surely is among three that solve the problem.

See "Problem Solving strategies" by Arthur Angel