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

Question

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

Does anyone know a simple/elementary proof?

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

Answer 2

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