Properties of Fermat primes

Fermat primes 17 and 257 appear a lot in the prime composition of numbers of the form $a^{2^n}+1$. For example, $11^8+1$ is divisible by 17 and $11^{32}+1$ is divisible by 257. I have verified the following statement for 3, 5, 17 and 257 but can't prove it. I would be grateful if someone could provide a hint.

Let $F = 2^{2^k} + 1$ be a Fermat prime.
Then for $n=0, 1, ..., 2^k-1, x^{2^n} + 1 \equiv 0 \mod F$ has exactly $2^n$ solutions.

For example, when k=2 we have:
$(n=0) \hspace{10pt} x^1 + 1 \equiv 0 \mod 17$ has one solution (x=16).
$(n=1) \hspace{10pt} x^2 + 1 \equiv 0 \mod 17$ has two solutions (x=4 and 13).
$(n=2) \hspace{10pt} x^4 + 1 \equiv 0 \mod 17$ has four solutions (x=2, 8, 9 and 15).
$(n=3) \hspace{10pt} x^8 + 1 \equiv 0 \mod 17$ has eight solutions (x=3, 5, 6, 7, 10, 11, 12 and 14).

This sort of rephrases Henning's answer. (That one is bottom up, this one is top down, which I like more personally)

Fermat's little theorem says that $x^{2^{2^k}}-1$ has $2^{2^k}$ solution mod $p$. Now $x^{2^{2^k}}-1 = \left (x^{2^{2^{k-1}}} - 1 \right)\left(x^{2^{2^{k-1}}} + 1 \right)$, each factor having at most $2^{2^{k-1}}$ solutions because the degree of each factor is $2^{2^{k-1}}$. As their product has $2^{2^k}$ solutions we are forced to conclude that each factor has exactly $2^{2^{k-1}}$ solutions.

Now take the factor $x^{2^{2^{k-1}}} - 1$ and repeat the same argument.

• +1 I have to agree on top-down being clearer. The bottom-up approach went fine until I noticed that I'd read the equation as $x^{2^n}=1$ instead of $x^{2^n}=-1$, and I had to scramble to recover some sense from my train of thought ... – Henning Makholm Sep 14 '11 at 17:42

Obviously $x^1+1\equiv 0 \pmod p$ has exactly one solution.

For each $n$ it must hold that $x^{2^{n+1}}+1\equiv 0 \pmod p$ has at most twice as many solutions as $x^{2^n}+1\equiv 0\pmod p$ -- otherwise one of the $2^n$th roots must have more than two square roots in $\mathbb F_p$, which is is impossible.

Fermat's little theorem ensures that $x^{2^{2^k}}\equiv 1\pmod p$ for all nonzero $x$. But this means that $x^{2^{(2^k-1)}}$ must always be a square root of $1$ modulo $p$, that is, either $1$ or $-1$. An analogous argument to the one above shows that there cannot be more than $2^{(2^k-1)}$ instances of either $1$ or $-1$, so that must be the number of solutions to $x^{2^{(2^k-1)}}+1\equiv 0\pmod p$. But that determines the number of $2^n$th roots of $-1$ uniquely for $1\le n\le 2^k-1$.

In general, this reasoning means that $x^{2^n}\equiv a \pmod p$ with $a\not\equiv 0$ always has either exactly $2^n$ solutions or none at all, depending on how many times one can square $a$ modulo $p$ without reaching $1$.

[Removed my previous generalization for this]

Even more general theorem, with even easier proof:

If $p$ is prime and $2d|p-1$, then the number of solutions of $x^d+1=0$ in $\mathbb{F}_p$ is $d$.

Proof:

Since $\mathbb{F}_p^\times$ is a cyclic group of order $p-1$, the number of solutions for $x^{2d}-1=0$ is $2d$, and the number of solutions of $x^d-1=0$ must be $d$, so the number of solutions of $x^d+1=0$ must be $d$.

This uses two pieces of knowledge:

Lemma: $\mathbb{F}_p^\times$ is a cyclic group of order $p-1$.

Lemma: If $G$ is a cylic group of order $n$ and $m|n$, the number of solutions to $x^m=1$ in $G$ is $m$.

Even more generally: If $a\in\mathbb{F}_p^\times$ is of order $n$ and $dn|p-1$, then the number of solutions to $x^d = a$ is $d$. (The previous theorem corresponds to the case $a=-1$ and $n=2$.)

Most generally: If $(C_m,\times)$ is a cyclic group of order $m$, and $a\in C_m$ is of order $n$, and $d\geq 1$, let $d_0=\gcd(m,d)$. Then $x^d=a$ has solutions in $C_m$ iff and only if $d_0n|m$, in which case, there will be exactly $d_0$ solutions.