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

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