(a) Show that $x^2 \equiv 3 \pmod {F_n}$ where the Fermat prime $F_n = 2^{2^n} + 1$ has no solutions for $n = 1, 2, 3$ and $4$.
(b) Prove that for any positive integer $n$
$$ F_n = 2^{2^n} + 1 \equiv 5 \pmod {12}$$
(a) The following table calculates $F_n \pmod {12}$ for $n=1,2,3,4$.
| n | F_n | F_n mod 12 |
| 1 | 5 | 5 |
| 2 | 17 | 5 |
| 3 | 257 | 5 |
| 4 | 65537 | 5 |
We proved the following result in the previous exercise. For odd prime $p$, we have
$$ (\frac{3}{p}) = \begin{cases} 1 & \text{ if } p \equiv 1 \text{ or } 11 \pmod {12} \\ -1 & \text{ if } p \equiv 5 \text{ or } 7 \pmod {12} \end{cases} $$
Since $F_n \pmod{12}=5$ in all cases, this result tells us $(\frac{3}{F_n})=-1$, and so by Euler's Criterion 3 is not a quadratic residue of $F_n$. That is, $x^2 \equiv 3 \pmod {F_n}$ has no solutions.
(b) We prove the result by induction.
Let $S(n)$ be the statement
$$ S(n) \quad := \quad F_n = 2^{2^n} + 1 \equiv 5 \pmod {12} $$
We need to prove a base case $S(1)$, and the inductive step $S(n) \implies S(n+1)$.
Base Case $S(1)$
We need to show that $F_1 \equiv 5 \pmod {12}$
$$ F_1 = 2^{2^1} + 1 = 4+1 = 5 \equiv 5 \pmod {12} $$
The base case is proven.
Inductive Step $S(n) \implies S(n+1)$
We assume $S(n)$ as the induction hypothesis. We aim to show $S(n+1)$.
$$ F(n+1) = 2^{2^{n+1}} +1 = 2^{2^n \times 2} + 1 = 2^{2^n +2^n} + 1 =(2^{2^n})\times (2^{2^n}) + 1 \equiv \underbrace{(4)\times(4)}_{S(n) \text{ applied twice}}+1 \equiv 17 \equiv 5 \pmod {12} $$
And so we have shown $S(n) \implies S(n+1)$.
By showing the base case and the inductive step, by induction we have proven that for all natural numbers $n$
$$ F_n = 2^{2^n} + 1 \equiv 5 \pmod {12}$$