Past exam of the mathematics course of the University of Cambridge / 2001 / ia / Paper 4 / 7E (Numbers and Sets)

If $p$ is a prime number and $p\nmid a$, multiplication by $a$ permutes the nonzero residue classes modulo $p$: $ai\equiv aj$ implies $i\equiv j$ because $a$ has a multiplicative inverse. Multiplying all the permuted classes givesThe factorial is a nonzero element of the finite field ${\mathbb{F}}_p$, so cancellation is valid. Thereforewhich is Fermat's little theorem.

Let $d$ be the multiplicative order of $a$ modulo $p$. Use Euclidean division to write $x=qd+r$, $0\le r<d$. Since $a^d\equiv 1$,If $a^x\equiv 1$, minimality of $d$ forces $r=0$, so $d$ divides $x$. Conversely, $d\mid x$ immediately gives $a^x\equiv 1$. For negative integers $x$, powers are interpreted using the multiplicative inverse and the same argument applies.

Apply the result to $x=p-1$, using Fermat's little theorem. Then $d\mid p-1$, equivalently

If $x^2\equiv -1(\mathrm{mod}p)$ with $p$ an odd prime, then $x^4\equiv 1$ but $x^2\not\equiv 1$. The multiplicative order consequently divides four and is neither one nor two, so it is four. The preceding divisibility result makes $4\mid p-1$ necessary.

For sufficiency, suppose $p\equiv 1(\mathrm{mod}4)$ and put $r=(p-1)/2$, an even integer. Pair opposite factors in the factorial:Wilson's theorem gives $(r!{)}^2\equiv -1(\mathrm{mod}p)$, explicitly producing a square root of minus one modulo a prime. Thus