= Solution
Suppose $x$ is a <quadratic nonresidue>. On the nonzero <residue classes> modulo $p$, define the <involution>
$$
T(a)=xa^{-1}.
$$
It 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,xa^{-1}\}$, each with product $x$. Consequently
$$
\prod_{a=1}^{p-1}a\equiv x^{(p-1)/2}\pmod p.
$$
Now 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$, so
$$
\boxed{x^{(p-1)/2}\equiv-1\pmod p.}
$$
Together with the preceding part, this is <Euler's criterion>; the pairing argument establishes the converse without assuming it.
Back to article page
