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

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.

For the odd prime $p$, the Fermat-Euler theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. Therefore the residue class $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv 0(\mathrm{mod}p)$. Since a prime number dividing a product divides one of its factors,If $x$ is a quadratic residue, choose $y$ with $y^2\equiv x(\mathrm{mod}p)$. Then $y$ is nonzero modulo $p$, and Fermat's little theorem givesThis proves the quadratic residue direction of Euler's criterion.

Suppose $x$ is a quadratic nonresidue. On the nonzero residue classes modulo $p$, define the involutionIt is an involution because $T(T(a))=a$. A fixed point would satisfy $a^2=x$, which is excluded by the quadratic nonresidue hypothesis. Thus it partitions the $p-1$ classes into $(p-1)/2$ disjoint pairs $\{a,x{a}^{-1}\}$, each with product $x$. ConsequentlyNow evaluate the same product by pairing every class with its own modular inverse. The only classes equal to their modular inverses solve $(a-1)(a+1)=0$ and hence are $1$ and $-1$. All other pairs have product one. The complete product is therefore $-1$, soTogether with the preceding part, this is Euler's criterion; the pairing argument establishes the converse without assuming it.

Fermat's little theorem reduces the exponent modulo $22$ because $23$ is a prime number and $5$ is coprime to it. Compute $5^2\equiv 3(\mathrm{mod}22)$, then $5^4\equiv 9(\mathrm{mod}22)$ and $5^5\equiv 45\equiv 1(\mathrm{mod}22)$. Thus $5^5=22k+1$ for an integer $k$, andThe exponent is $5^5=3125$, rather than an iterated left-associated power.