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?
Best Answer
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).