2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ What is your question? $\endgroup$ – David Apr 17 '15 at 5:31
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Apr 17 '15 at 5:35
  • 1
    $\begingroup$ Andre - Ah that was so simple, thanks! I didn't think of it that way. David - Sorry, I accidentally edited over - "Prove this statement!" $\endgroup$ – Rohit Apr 17 '15 at 5:42
  • 1
    $\begingroup$ @Rohit That's not a question, either. $\endgroup$ – user147263 Apr 17 '15 at 6:06
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.