Past exam of the mathematics course of the University of Cambridge / 2014 / ia / Paper 4 / 6E / iii / Solution

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.