<s>[INST] 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).
 [/INST] 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.
</s>