Let $r$ be a primitive root of an odd prime $p$.
(a) Prove that $r^{2n}$ is a quadratic residue of $p$.
(b) Prove that $r^{2n+1}$ is a quadratic non-residue of $p$.
(c) By using the primitive root $r$ show that there are $\frac{p− 1}{2}$ quadratic residues and $\frac{p− 1}{2}$ quadratic non-residues of $p$.
(a) We can see immediately that $r^n$ is a solution to $x \equiv r^{2n} \pmod p$, and so $r^{2n}$ is a quadratic residue of $p$.
(b) By the multiplicative property of the Legendre symbol, we need to show that $r$ is a quadratic non-residue, since $r^{2n}$ is a quadratic residue.
For the purpose of contradiction, we'll assume $r$ is a quadratic residue, and so by Euler's Criterion
$$ r^{\frac{p-1}{2}} \equiv 1 \pmod p $$
This is a contradiction because $r$ is a primitive root, and the smallest index $j$ such that $r^j \equiv 1 \pmod p$ must be $r=p-1$.
And so any primitive root is not a quadratic residue.
(c) We know from a previous exercise that the set
$$ S = \{ r^0, r^1, r^3, \ldots, r^{p-1} \} $$
is congruent to the set
$$ T = \{ 1, 2, 3, \ldots, (p-1) \} $$
We also know that even powers of the primitive root $r$ are quadratic residues, and that odd powers are quadratic non-residues.
There are $\frac{p-1}{2}$ elements of the set $S$ which have even powers. This means there are $\frac{p-1}{2}$ elements of the set $T$ which are quadratic residues.
By a symmetric argument there are $\frac{p-1}{2}$ elements of the set $T$ are quadratic non-residues.
And so we have shown there are $\frac{p− 1}{2}$ quadratic residues and $\frac{p− 1}{2}$ quadratic non-residues of $p$.