elementary number theory - 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.