2
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

All quadratic residues modulo $p$ are of the form $(r^n)^2 = r^{2n}$, so all odd powers of $r$ must be nonresidues.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Numbersandsoon Nov 19 '13 at 7:18
  • $\begingroup$ Yes, I'm writing $x = r^n$, as any element $x$ mod $p$ can be written in this form. $\endgroup$ – Arthur Nov 19 '13 at 7:31
  • $\begingroup$ 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? $\endgroup$ – Alessar Dec 5 '18 at 11:38

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.