Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Does anyone know a simple/elementary proof?

share|improve this question

1 Answer 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).

share|improve this answer
    
To be more precise: the claim only holds for $n\ge2$. For $n=0$ or $n=1$ the claim does not hold. –  Jyrki Lahtonen Dec 14 '11 at 13:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.