# How to prove that if a prime $p$ 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?

• This is a special case of this question. Apr 21, 2015 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 factor two comes from the fact that at this point we know $$p\equiv 1\pmod 8$$ (save for 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).

• To be more precise: the claim only holds for $n\ge2$. For $n=0$ or $n=1$ the claim does not hold. Dec 14, 2011 at 13:37

Here's an explanation that avoids group theory and gives a pointer to the number theory results used.

To start with: we know that $$2$$ has a multiplicative order $$\text{ord}_p(2)$$ such that $$2^m \equiv 1 \pmod p$$ if and only if $$m$$ is a multiple of $$\text{ord}_p(2)$$. We are given that $$p$$ divides $$2^{2^n} + 1$$; therefore $$2^{2^n} \equiv -1 \pmod p$$ and (squaring that) $$2^{2^{n+1}} \equiv 1 \pmod p$$. Therefore $$2^{n+1}$$ is a multiple of $$\text{ord}_p(2)$$, but $$2^n$$ is not; this can only happen if $$\text{ord}_p(2) = 2^{n+1}$$.

By Fermat's little theorem, we know that for any prime $$p$$, $$2^{p-1} \equiv 1 \pmod p$$. Therefore $$p-1$$ is a multiple of $$\text{ord}_p(2) = 2^{n+1}$$. This tells us that $$p = k \cdot 2^{n+1} + 1$$ for some $$k$$, which is almost what we want; we just want to show that $$k$$ is even.

To do this, we turn to quadratic residues: the question of when $$x^2 \equiv a \pmod p$$ has a solution $$x$$. By Euler's criterion, a solution exists if and only if $$a^{\frac{p-1}{2}} \equiv 1 \pmod p$$. In our particular case, does $$x^2 \equiv 2 \pmod p$$ have a solution? Applying Euler's criterion, we test if $$2^{\frac{p-1}{2}} = 2^{k \cdot 2^n} \equiv 1 \pmod p$$. Well, $$2^{2^n} \equiv -1 \pmod p$$, so $$2^{k \cdot 2^n} \equiv (-1)^k \pmod p$$. So we conclude that $$x^2 \equiv 2 \pmod p$$ has a solution if and only if $$k$$ is even.

Finally, by the $$\pm 2$$ supplement to the law of quadratic reciprocity, we have a second way of testing if $$x^2 \equiv 2 \pmod p$$ has a solution: this happens if and only if $$p \equiv \pm 1 \pmod 8$$. In our case, $$k \cdot 2^{n+1} +1 \equiv 1 \pmod 8$$ as long as $$n \ge 2$$. Therefore $$x^2 \equiv 2 \pmod p$$ must have a solution, and from the previous paragraph, $$k$$ must be even, finishing the proof.

(The result does not hold for $$2^{2^0} +1 = 3$$ and $$2^{2^1} = 5$$, since these are prime themselves, but do not have the correct form.)