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

For a prime number $p$, every nonzero residue class has a unique multiplicative inverse modulo $p$: Bezout identity supplies one because its representative is coprime to $p$, and cancellation modulo a prime gives uniqueness. Pair each residue with its inverse. The only unpaired residues satisfy $a^2\equiv 1$, so $p\mid (a-1)(a+1)$; the Euclid lemma gives $a\equiv 1$ or $-1$. For odd $p$, these are distinct. Every other pair contributes one to the product of all nonzero residues, leavingFor $p=2$, $1!\equiv -1(\mathrm{mod}2)$ as well. This proves Wilson theorem in all cases.

For an odd prime, set $q=(p-1)/2$. Pair the upper half of the factorial with the negatives of the lower half:If $p\equiv 1(\mathrm{mod}4)$, then $q$ is even. ThereforeThis constructs a square root of minus one modulo a prime explicitly.

The modular congruence $x^4\equiv 1$ first implies $x\not\equiv 0$. Multiplication by such an $x$ permutes the nonzero residue classes modulo the prime $p$: if $xa\equiv xb$, cancellation gives $a\equiv b$. Multiply all these residues and cancel their nonzero product to obtain $x^{p-1}\equiv 1$, the usual short proof of Fermat little theorem.

Now $(x^2-1)(x^2+1)\equiv 0$. By the Euclid lemma, either $x^2\equiv 1$ or $x^2\equiv -1$. In the latter case, because $p-1=4k+2$,contradicting the preceding product argument, since $p$ is odd. ThusNo unproved assertion about the number of fourth roots is needed.

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.