3
$\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$

1 Answer 1

Reset to default
4
$\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$
3
  • $\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, 2013 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, 2013 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, 2018 at 11:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .