This is another number theory problem I've been tackling:
Let $p$ be an odd prime number and let $r$ be a primitive root modulo
$p$. Prove that the quadratic residues modulo $p$ are congruent to the
even powers of $r$ modulo $p$ and the quadratic nonresidues modulo $p$
are congruent to the odd powers of $r$ modulo $p$.
We know that quadratic residues $a$ satisfy $x^2 \equiv a \mod p$. We must show that $a \equiv r^{2k} \mod p$, i.e. that $r^{2k}$ is congruent to a square modulo $p$. Letting $x=r^k$ we see that the equality holds. I'm not sure how to proceed from here!
Best Answer
All quadratic residues modulo $p$ are of the form $(r^n)^2 = r^{2n}$, so all odd powers of $r$ must be nonresidues.