4.II.7E

(a) Prove that, if $p$ is prime and $a$ is not a multiple of $p$, then $a^{p-1} \equiv 1(\bmod p)$.

(b) The order of $a(\bmod p)$ is the least positive integer $d$ such that $a^{d} \equiv 1(\bmod p)$. Suppose now that $a^{x} \equiv 1(\bmod p)$; what can you say about $x$ in terms of $d$ ? Show that $p \equiv 1(\bmod d)$.

(c) Suppose that $p$ is an odd prime. What is the order of $x(\bmod p)$ if $x^{2} \equiv-1(\bmod p)$ ? Find a condition on $p(\bmod 4)$ that is equivalent to the existence of an integer $x$ with $x^{2} \equiv-1(\bmod p)$.

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