# Quadratic residues modulo $p$ are congruent to the even powers of $r$ modulo $p$

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!

All quadratic residues modulo $p$ are of the form $(r^n)^2 = r^{2n}$, so all odd powers of $r$ must be nonresidues.
• Aha, so you're letting $x=r^n$ in the congruence $x^2 \equiv a \mod p$? Is this the 'right' way to think about it? – Numbersandsoon Nov 19 '13 at 7:18
• Yes, I'm writing $x = r^n$, as any element $x$ mod $p$ can be written in this form. – Arthur Nov 19 '13 at 7:31
• So from definition of PR $r^{\phi(p)} \equiv 1 mod p$ I can write $r^{2k} \equiv 1 mod p$ , because $p-1$ will be always even and by QR definition, it's done in this way? – Alessar Dec 5 '18 at 11:38