# Lucas' result regarding Fermat numbers

Can anyone provide a proof that $\forall$ primes $p$, $$\quad p\mid 2^{2^{n}}+1 \implies 2^{n+2} \mid p-1\quad ?$$ I can prove that $p\mid 2^{2^{n}}+1 \implies 2^{n+1} \mid p-1$ using the order of $2$ modulo $p$, and think that quadratic residues might do it, but I have not yet managed it.

Thank you very much.

-
I've corrected the statement of your question (powers of $2$ are rarely factors of prime numbers...) –  Zev Chonoles Jun 13 '13 at 19:09
Euler proved that every factor of Fn must have the form k2n+1 + 1 (later improved to k2n+2 + 1 by Lucas). en.wikipedia.org/wiki/Fermat_number#Primality_of_Fermat_numbers –  Will Jagy Jun 13 '13 at 19:11
You need to add the hypothesis $n \ge 2$; the statement is false for $n = 0$ or $1$. Then you know from what you have already that $8\mid p - 1$, which means $2$ is a quadratic residue mod $p$. Can you take it from there? –  FredH Jun 17 '13 at 5:52
@FredH: thank you very much. I missed the fact that $2$ being a quadratic residue meant $2^{\frac{p-1}{2}} \equiv 1 \mod p$ which using that $2^{2^{n}} \equiv -1 \mod p$ meant that since $p=m*2^{n+1}+1$, $m$ must be even as required. –  Frill Jun 20 '13 at 18:33