This question often comes in my mind when doing exercices in elementary number theory:
Is every non-square integer a primitive root modulo some odd prime?
This would make many exercices much easier. Unfortunately I seem unable to discover anything interesting which may lead to an answer.
It seems likely to me that this is true. If $n\equiv2\pmod3$ then it's a primitive root modulo $3$. If $n\equiv2,3\pmod5$, it's a primitive root modulo $5$. If we would continue like this, my guess is that any non-square $n$ will satify at least one of these congruences.
This being difficult, I began considering a simplified question:
Is every non-square integer a quadratic non-residue modulo some prime?
Or equivalently,
If an integer is a square modulo every prime, then is it a square itself?
The second form seems easier to approach, however I still can't find anything helpful.
Best Answer
Let $n$ be a non-square. Write $n=a^2b$ with $b\ne 1$ square-free. Write $b=p_1\cdot\ldots\cdot p_m$ as product of disctinct primes with $m\ge 1$. For primes $q> n$ the factor $a^2$ can be ignored, so we have that $\left( \frac bq\right)=1$ for almost all primes $q$. According to quadratic reciprocity law, $ \left(\frac{b}{q}\right)$ is determined by $q\bmod 8b$. Also, there is at least one residue $d\bmod 8b$ for which $q\equiv d\pmod{8b}$ implies $ \left(\frac{b}{q}\right)=-1$ (e.g. ensure $\left(\frac d{p_1}\right)=-1$ and $\left(\frac d{p_i}\right)=+1$ for all other $i$ and use the chinese remainder theorem). Especially, $d$ is relatively prime to $8b$ so that by Dirichlet there exist infinitely many primes $q$ with $q\equiv d\pmod{8b}$. For such a $q$ with $q>n$ we conclude that $n$ is not a square modulo $q$.