Is every non-square integer a primitive root modulo some odd prime? 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.
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&gt; 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&gt;n$ we conclude that $n$ is not a square modulo $q$.
Your "equivalent" question seems trivial and therefore not equivalent. 

"If an integer is a square modulo every prime, then is it a square itself?"

Given an integer n, there is a prime p > n. If n is a square modulo every prime, including p, then n = n (modulo p) is a square, so n is a square. 

BTW. I wrote a short program that checked whether every non-square integer n &lt;= N is the primitive root modulo some prime p > N, with N = 40 x 10^9. It found that actually every non-square n &lt;= N is a primitive root modulo some prime p with N &lt; p &lt;= N + 1357, which is just the 55th prime > N. This seems to indicate that it is more promising to look for a proof than for a counterexample.