Can a number be a quadratic residue modulo all prime that do not divide it

Question

Is there a proof that for any number $a$, there must be at least one prime $p$ such that $(a/p)=-1$, where $(a/p)$ is the Legendre symbol?

In other words, for all $a$, is there at least one prime $p$ such that $a$ is a quadratic nonresidue modulo $p$?

EDIT: Due to the comments pointing out that there is no such $p$ for $a=x^2$, my question remains the same, except for only all $a\neq x^2$.

Answer 1

Here is an interesting exercise that appears in A Classical Introduction to Modern Number Theory.

Let $a$ be a non square integer. Then there are infinitely many primes $p$ for which $a$ is a quadratic non residue.

As a hint, use the Chinese Remainder Theorem in a clever way.

Answer 2

Here is a solution to the above post.

Set $a=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ be prime decomposition of $a$. Clearly, there is a $j$ such that, $\alpha_j$ is odd. Without loss of generality, assume $j=1$. Also, suppose $p_1\neq 2$, which is a case that can be handled separately.

We will construct a prime $p$, such that $p$ is a quadratic residue modulo $p_i$, for every $i \geq 2$, and is not a quadratic residue in modulo $p_1$. Take $a_1$ to be a quadratic non-residue in modulo $p_1$. Take $q_2,\dots,q_k$ to be quadratic residues in modulo $p_k$. Now, there is a prime $p$ such that $p\equiv a_1\pmod{p_1}$, and $p\equiv q_i\pmod{p_i}$, and $p\equiv 1\pmod{4}$, for $i \geq 2$. Existence of this prime is due to Chinese remainder theorem + Dirichlet's theorem.

Finally, by quadratic reciprocity, it is not hard to check, $p$ is a quadratic residue in mod $p_j$ for $j\geq 2$, and a non-residue in mod $p_1$. Construction is complete.