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

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$$.

• What about $a=1$? – Somos Dec 30 '18 at 0:39
• Or any other square, for that matter. – Robert Israel Dec 30 '18 at 0:42
• See here and its linked questions for related results. – Bill Dubuque Dec 30 '18 at 23:00

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.

• Thank you for the reference. May you provide a proof of the exercise as the book is behind a pay barrier? – Tejas Rao Dec 30 '18 at 2:08
• Try your best and after a few days I can give you another hint if needed. – Sandeep Silwal Dec 30 '18 at 2:11

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.