# Relationship between primitive roots and quadratic residues

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.

## 2 Answers

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.

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

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