Let $r$ be a primitive root $\mod\ p$ and let $k$ be a positive integer. Show that $r^k$ is a quadratic residue $\mod\;p$ if and only if $k$ is even So one direction is easy. If $k$ is even, then let $k=2m$ for some integer $m$. Then, $(r^k)^{(p-1)/2}≡r^{m(p-1)}≡1^m≡1\;\pmod{p}$, since $r$ is a primitive root $\mod{p}$. So therefore $r^k$ is a quadratic residue $\mod{p}$ if $k$ is even.
However, the other direction I'm having a little trouble with. I know that if $r^k$ is a quadratic residue $\mod\;p$, then $(r^k)^{(p-1)/2}≡1\;\pmod{p}$ has a solution. And we also know that since $r$ is a primitive root $\mod p$, that $r^{p-1}≡1\;\pmod{p}$. So therefore, $(r^k)^{(p-1)/2}≡r^{p-1} \pmod{p}$. But now I am stuck on how to prove that k must be even.
 A: We have $$r^{(p-1)/2}\ne 1\mod p$$ because $r$ is a primitive root modulo $p$. Hence $r$ is not a quadratic residue modulo $p$. 
Would $r^k$ with odd $k$ be a quadratic residue modulo $p$, $r$ would be a quadratic residue modulo $p$ as well, but we just have shown that this is impossible.
Hence $k$ must be even.
A: There are exactly $(p-1)/2$ quadratic residues $mod\;p$. [That's because $x²=a \; (mod \; p)$ has either zero or two solutions for x].
Because $r$ is a primitive root modulo $p$, $|<r^{2i}>| = (p-1)/2$. Further, all elements in this group are of the form $r^{k}$, where $k$ is even, so as you just showed, all those elements are quadratic residues.
That means we have already found all the $(p-1)/2$ quadratic residues modulo $p$ by calculating all even powers of $r$.
Finally, because $r$ is a primitive root, an odd power and an even power of $r$ can't be equal modulo $p$. Hence there are no odd powers of $r$, that are quadratic residues. Hence all quadratic residues residues modulo $p$ are even powers of $r$.
