# Every primitive root modulo an odd prime is a quadratic nonresidue

This is my proof of the title statement. Is it correct?

Suppose $a$ is a primitive root and quadratic residue modulo $p$. Then by definition $$\operatorname{ord}_p(a)=p-1$$ But Euler's criterion states that $$a^{(p-1)/2}\equiv1\bmod p$$ which is impossible ($\frac{p-1}2<p-1$ for all odd primes $p$) and leads to a contradiction. Therefore, every primitive root is a quadratic nonresidue modulo an odd prime $p$.

I have another question. Is every quadratic nonresidue a primitive root?

• Your proof is correct, provided that you can argue why your congruence is impossible. But the converse does not hold: not every quadratic nonresidue is a primitive root. There are $\left(p-1\right)/2$ quadratic nonresidues but only $\varphi\left(p-1\right)$ primitive roots. – darij grinberg Oct 24 '16 at 4:30
• For your last question, note that if $p\equiv3\pmod4$ then $-1$ is a quadratic nonresidue that is never a primitive root if $p>3$. You could also simply enumerate the primitive roots and quadratic (non)residues modulo $13$, for example, to gain some insight. – Greg Martin Oct 24 '16 at 4:46

Using Euler's criterion might be correct but seems a little overpowered. You could fairly easily achieve the result by assuming that $a$ is a quadratic residue and then considering the order of $b$ (defined by $b^2 \equiv a \bmod p$):
Suppose $b$ is a primitive root. Then $b^{p-1}\equiv 1 \bmod p$, but since we know that $p-1$ is even, it will be the case that $a^{(p-1)/2} \equiv b^{p-1}\equiv 1$ also, so $a$ is not a primitive root.
Now suppose $b$ is not a primitive root; therefore there is some $k<p-1$ such that $b^k \equiv 1$. Then $a^k \equiv b^{2k} \equiv 1^2 \equiv 1$ and $a$ is again not a primitive root.
This gives us: $a$ is a quadratic residue$\bmod p \implies a$ is not a primitive root$\bmod p$. Since $a$ cannot be both a quadratic residue and a primitive root, this proves the title claim.
To answer your other question, consider a prime $p>3$ with $p\equiv 3 \bmod 4$. Then $-1$ is a quadratic nonresidue but is of course not a primitive root. (In general there are plenty of quadratic nonresidues that are not primitive roots, but this is easy to demonstrate).