Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Does anyone know a simple/elementary proof?

share|cite|improve this question
This is a special case of this question. – Jyrki Lahtonen Apr 21 '15 at 9:20

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|cite|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


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.