Past exam of the mathematics course of the University of Cambridge / 2026 / ia / Paper 4 / 6D (Numbers and Sets)

For $a\ne 0(\mathrm{mod}p)$, $\gcd (a,p)=1$, so Bézout gives $au+pv=1$ and $u$ is an inverse modulo $p$.

If $x^2\equiv a$ and $y^2\equiv a(\mathrm{mod}p)$, then $(x-y)(x+y)\equiv 0$, hence $y\equiv \pm x$; these differ for odd $p$. It fails for composite moduli: $1$ has four square roots modulo $8$.

For prime $n$, pair each nonzero residue with its inverse; only $\pm 1$ are self-inverse, yielding Wilson theorem. Conversely, if $(n-1)!\equiv -1(\mathrm{mod}n)$, every $1\le a<n$ is a unit (otherwise a common divisor would divide the left side and $n$ but not $-1$), so $n$ is prime.

Wilson gives $18!\equiv -1(\mathrm{mod}19)$. Since $18\cdot 17\equiv 2$, $2\cdot 16!\equiv -1$, hence $16!\equiv 9(\mathrm{mod}19)$.

By Fermat, $a^{p-1}=1$. Thus $a^{(p-1)/2}=\pm 1$. The squaring map on ${\mathbb{F}}_p^{\ast }$ has kernel $\{\pm 1\}$, so exactly $(p-1)/2$ inputs are squares; the polynomial $x^{(p-1)/2}-1$ has at most that many roots and already has all squares, proving the two cases.