# If $r$ is a primitive root of an odd prime $p$, then $s$ is a residue of $p$ iff $s \equiv r^{2n} \pmod{p}$.

If $r$ is a primitive root of an odd prime $p$, then prove that $s$ is a residue of $p$ iff $s \equiv r^{2n} \pmod{p}$.

The above was the original statement of an elementary number theory question, the answer to which I didn't know where to begin since I was confused. The answer based on Andre's comment is (and I hope this is correct and precise) as follows:

Given $r$ is a primitive root of $p$, it follows that $r^{p-1} \equiv 1 \pmod{p}$. Given $s$ is a residue of $p$, it follows that $s^{(p-1)/2} \equiv 1 \pmod{p}$. By transitivity of congruences $s^{(p-1)/2} \equiv r^{p-1} \pmod{p}$. Thus it follows that $s \equiv r^{2n} \pmod{p}$ or that $s$ is an even power of $r$ modulo $p$.

Given $s \equiv r^{2n} \pmod{p}$ for some integer $n$. Taking both sides to the power $\phi(p)$ we obtain $s^{\phi(p)} \equiv r^{2n\phi(p)} \pmod{p}$. Taking a square root on both sides we obtain $s^{\phi(p)/2} \equiv r^{n\phi(p)} \pmod{p}$, which reduces to $s^{\phi(p)/2} \equiv (r^{\phi(p)})^n \pmod{p}$. Since $r$ is a primitive root of $p$ it follows that $r^{\phi(p)} \equiv 1 \pmod{p}$, and therefore $s^{\phi(p)/2} \equiv (1)^n \pmod{p}$. Thus $s^{(p-1)/2} \equiv 1 \pmod{p}$, (since $\phi(p) = p-1$ for an odd prime), and by the definition of a quadratic residue this implies that $s$ is a quadratic residue mod $p$.

• What is your question? – David Apr 17 '15 at 5:31
• The even powers of $r$ are obviously quadratic residues of $p$. There are $\frac{p-1}{2}$ distinct (modulo $p$) even powers of $r$, and there are $\frac{p-1}{2}$ quadratic residues, so the even powers of $r$ must be all of the quadratic residues. – André Nicolas Apr 17 '15 at 5:35
• Andre - Ah that was so simple, thanks! I didn't think of it that way. David - Sorry, I accidentally edited over - "Prove this statement!" – Rohit Apr 17 '15 at 5:42
• @Rohit That's not a question, either. – user147263 Apr 17 '15 at 6:06

Given $r$ is a primitive root of $p$, it follows that $r^{p-1} \equiv 1 \pmod{p}$. Given $s$ is a residue of $p$, it follows that $s^{(p-1)/2} \equiv 1 \pmod{p}$. By transitivity of congruences $s^{(p-1)/2} \equiv r^{p-1} \pmod{p}$. Thus it follows that $s \equiv r^{2n} \pmod{p}$ or that $s$ is an even power of $r$ modulo $p$. $\blacksquare$

Given $s \equiv r^{2n} \pmod{p}$ for some integer $n$. Taking both sides to the power $\phi(p)$ we obtain $s^{\phi(p)} \equiv r^{2n\phi(p)} \pmod{p}$. Taking a square root on both sides we obtain $s^{\phi(p)/2} \equiv r^{n\phi(p)} \pmod{p}$, which reduces to $s^{\phi(p)/2} \equiv (r^{\phi(p)})^n \pmod{p}$. Since $r$ is a primitive root of $p$ it follows that $r^{\phi(p)} \equiv 1 \pmod{p}$, and therefore $s^{\phi(p)/2} \equiv (1)^n \pmod{p}$. Thus $s^{(p-1)/2} \equiv 1 \pmod{p}$, since $\phi(p) = p-1$ for an odd prime, and by the definition of a quadratic residue this implies that $s$ is a quadratic residue mod $p$. $\blacksquare$