How to prove that if a prime divides a Fermat Number then $p=k\cdot 2^{n+2}+1$?

If a prime $p$ divides a Fermat Number then $p=k\cdot 2^{n+2}+1$?

Does anyone know a simple/elementary proof?

Solution 1:

If $p\mid 2^{2^n}+1$, then $2^{2^n}\equiv -1\pmod p$. Together with the obvious corollary $2^{2^{n+1}}\equiv 1\pmod p$ this implies that the order of the residue class of $2$ in the multiplicative group $\mathbf{Z}_p^*$ is equal to $2^{n+1}$. This already implies that $2^{n+1}\mid p-1$, because the order of the group $\mathbf{Z}_p^*$ is equal to $p-1$, and by Lagrange's theorem the order of any element is a factor of the order of the group.

The remaining two comes from the fact that at this point we know $p\equiv 1\pmod 8$ (save the few smallest values of $n$ that are not interesting here). This tells us that $2$ itself is a quadratic residue modulo $p$. Therefore $2\equiv a^2\pmod p$ for some integer $a$. The order of $a$ in the group $\mathbf{Z}_p^*$ is thus $2^{n+2}$. The claim follows from this (Lagrange's theorem).