Help understanding proof: if $2^n + 1$ is prime the $n$ is a power of $2$ Reading this proof (and other proofs):
If $2^n+1$ is prime, why must $n$ be a power of $2$?
I don't understand why if we suppose $n$ is not a power of $2$ ($\forall k\in \mathbb{N}, 2^k \neq n$), then why $n = a \cdot 2^m$. How is this true? Aren't we discarding $n$ being odd?
Thanks for your help
 A: Observe that $x^{2k+1}+1$ has $-1$ as a root, so that you can factor out the term $(x+1)$. In fact, we can always write (just doing the long division)
$$
(x^{2k+1}+1) = (x+1)(x^{2k}-x^{2k-1}+x^{2k-2}-x^{2k-3}+\cdots +1).
$$
As pointed out in the comments, if $n$ is not a power of $2$, then it is divisible by an odd number, so we can write $n = (2k+1)\cdot m$ for some integer $m$. This means (using our above factorization with $x = 2^m$)that
$$
2^{n}+1 = \left(2^{m}\right)^{2k+1}+1 = (2^{m}+1)\cdot(2^{2k}-2^{2k-1}+\cdots +1)
$$
so that $2^n+1$ isn't prime since you just found a pair of nontrivial divisors.
A: If $p=2^h+1$ and $e$ is the least exponent such that $2^e\equiv 1\pmod{p}$ then $2^h=p-1<p$; $2^e>p$, so $h<e$. We have $2^{2^h}\equiv2^{p-1}\equiv1\pmod{p}$ and $2^h= p-1\equiv -1\pmod{p}$ and if $g<h$, $2^g\not\equiv-1\pmod{p}$ since $p\nmid2^g+1<p$. Now $2^e\cdot2^h=2^{e+h}\equiv-1\pmod{p}$ and $2^{e-h}\equiv-1\pmod{p}$, but $e-h\not< h$, $e-h\ge h$ or $e\ge 2h$. Squaring $(2^h)^2=2^{2h}\equiv1\pmod{p}$, which since $e\ge2h$ implies $e=2h$. Now $e\mid p-1=2^h=2^{e/2}$. Therefore $e=2^{a+1}$ so $p=2^{2^a}+1$, i.e., $h=2^a$, as desired.
In another direction, if $h$ is divisible by an odd number, say $h=h'(2n+1)$, then $2^{h'}+1\mid 2^h+1$ so $2^h+1$ cannot be prime in this case.
