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

The Fermat-Euler theorem states that for an integer $a$ and a positive integer $n$ with $\gcd (a,n)=1$,where the Euler totient function $\phi (n)$ counts the residue classes coprime to $n$. For $n\ge 2$, choose a reduced residue system $r_1,\dots ,r_{\phi (n)}$. Multiplication by the unit modulo n $a$ preserves coprimality and is injective on these residue classes: $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$, because $a$ has a multiplicative inverse modulo $n$. It therefore permutes the reduced residue system, givingThe product is also a unit modulo n, so it can be cancelled. This proves the Fermat-Euler theorem. For $n=1$ every modular congruence is automatic; one may use $\phi (1)=1$.

For a prime number $p$, the Euler totient function has value $\phi (p)=p-1$. Thus $a^{p-1}\equiv 1(\mathrm{mod}p)$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of Fermat's little theorem:Finally, Wilson theorem states that for every prime number $p$, $\boxed{(p-1)!\equiv -1(\mathrm{mod}p)}$. Its converse is also true: an integer $n>1$ is prime exactly when $(n-1)!\equiv -1(\mathrm{mod}n)$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.

Suppose $X^2\equiv -1(\mathrm{mod}p)$. Then $X$ is a unit modulo n for modulus $p$, and Fermat's little theorem impliesSince $p$ is an odd prime number, $1$ and $-1$ are distinct residue classes. Therefore $(p-1)/2$ is even, and $p\equiv 1(\mathrm{mod}4)$.

Conversely, put $q=(p-1)/2$. Pair each integer $j\in \{1,\dots ,q\}$ with $p-j$ in the factorial. Wilson theorem yieldsWhen $p\equiv 1(\mathrm{mod}4)$, $q$ is even, so $X=q!$ satisfies $X^2\equiv -1(\mathrm{mod}p)$. This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. HenceThe two solutions are $q!$ and $-q!$ modulo $p$: their difference is nonzero, and factoring $X^2-Y^2$ shows that a degree-two polynomial over the field of residues modulo $p$ has no further roots.

Split the factorial at $h$, using $k=p-1-h$:By Wilson theorem, this is $-1$. Therefore $h!k!\equiv (-1{)}^{k+1}(\mathrm{mod}p)$. If the prime number $p$ is odd, then $h+k=p-1$ is even, so $(-1{)}^k=(-1{)}^h$ andFor $p=2$, the signs $1$ and $-1$ are identical modulo $2$, and the two possibilities $(h,k)=(0,1),(1,0)$ also give the same result. The empty product convention $0!=1$ includes the endpoint cases. This is the complementary factorial congruence.