Past exam of the mathematics course of the University of Cambridge / 2003 / ia / Paper 4 / 6C / iii

For $p\equiv 1(\mathrm{mod}4)$, part (i) constructs a solution $a=q!$ to $a^2\equiv -1$. It is nonzero modulo $p$, so $a$ and $-a$ are distinct for odd $p$. Any other solution $x$ obeysThe Euclid lemma forces $x\equiv a$ or $-a$. Hence there are exactly two solutions. For $p\equiv 3(\mathrm{mod}4)$, a solution to $x^2\equiv -1$ would have $x^4\equiv 1$, but part (ii) would imply $x^2\equiv 1$, impossible because $p$ cannot divide two. ThereforeThese two cases exhaust all odd primes.