3
$\begingroup$

I understand that if $g$ is a primitive root modulo an odd prime $p$, then Euler's Criterion tells us that $g$ cannot be a quadratic residue.

My question is, does this result generalize to prime powers? That is, if $g$ is a primitive root modulo $p^m$ for an odd prime $p$, must $g$ be a quadratic non-residue?

I spent a little while trying to come up with a proof but was unable to achieve anything useful so any proofs (or counterexamples) are welcome.

$\endgroup$
4
$\begingroup$

The order of a quadratic residue modulo $n$ divides $\varphi(n)/2$. A primitive root has order $\varphi(n)$. Hence a primitive root is always a quadratic nonresidue.

$\endgroup$
  • $\begingroup$ Looks like you beat me by 11 seconds :) $\endgroup$ – Old John Dec 1 '13 at 23:54
  • $\begingroup$ Ahh so simple I cannot believe I did not see this! Thank you $\endgroup$ – user112750 Dec 1 '13 at 23:56
1
$\begingroup$

If $g$ is a primitive root, then the quadratic residues are precisely those elements which are even powers of $g$, so that if $g$ is a primitive root, then it cannot be a quadratic residue (since $g$ is an odd power of $g$) .

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