Paper 4, Section II, D

State Fermat's Theorem and Wilson's Theorem.

For which prime numbers $p$ does the equation $x^{2} \equiv-1(\bmod p)$ have a solution? Justify your answer.

For a prime number $p$, and an integer $x$ that is not a multiple of $p$, the order of $x$ $(\bmod p)$ is the least positive integer $d$ such that $x^{d} \equiv 1(\bmod p)$. Show that if $x$ has order $d$ and also $x^{k} \equiv 1(\bmod p)$ then $d$ must divide $k$.

For a positive integer $n$, let $F_{n}=2^{2^{n}}+1$. If $p$ is a prime factor of $F_{n}$, determine the order of $2(\bmod p)$. Hence show that the $F_{n}$ are pairwise coprime.

Show that if $p$ is a prime of the form $4 k+3$ then $p$ cannot be a factor of any $F_{n}$. Give, with justification, a prime $p$ of the form $4 k+1$ such that $p$ is not a factor of any $F_{n}$.

*Typos? Please submit corrections to this page on GitHub.*