For $n$ an odd, positive, square-free integer, there exists an odd prime $p$ with $\left( \frac{n}{p} \right) = -1$

Question

I'd like to prove that for $n$ an odd, positive, square-free integer, there exists an odd prime $p$ with $\left( \frac{n}{p} \right) = -1$

I'm drawing a complete blank here. Any help would be appreciated!

Thanks

Answer 1

To spell out some of what's in the comments:

Suppose that the Legendre symbol is 1 for all odd primes.

Then in particular it is 1 for all odd primes congruent to 1 modulo 4.

So by quadratic reciprocity, every prime congruent 1 mod 4 is a quadratic residue modulo n.

But given any b relatively prime to n, there is a prime congruent to b modulo n and congruent to 1 modulo 4 (using Dirichlet's Theorem on primes in arithmetic progressions, and the Chinese Remainder Theorem). The prime being 1 modulo 4 implies it's a quadratic residue modulo n, and the prime being b modulo n then says b is a quadratic residue modulo n, so we have just proved that every residue modulo n is a quadratic residue modulo n. But this is nonsense; it's easy to show that there are quadratic nonresidues modulo n.