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

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

-
I would try using quadratic reciprocity and the infinitude of primes in arithmetic progressions with step coprime to the first element. Something like insisting that $p\equiv 1\pmod4$ and $p\equiv a_i\mod {p_i}$ for all prime factors $a_i$ of $n$, and suitably specified residues $a_i$. Reciprocity and $p\equiv 1\pmod4$ implies that $$\left(\frac {a_i} p\right)=\left(\frac p {a_i}\right).$$ – Jyrki Lahtonen May 20 '12 at 16:31
OOOOOPPSS! Substitute $p_i$ for $a_i$ on the last line. I would rewrite the comment, but need to catch a taxi to the airport in 5. See y'all! – Jyrki Lahtonen May 20 '12 at 16:46
Hint See this long interesting 1998/5/13 sci.math thread square in every $\mathbb Z/m$ implies square? – Bill Dubuque May 20 '12 at 16:54
@Bill, long, yes, but only 13 of the 61 messages in that thread were on-topic. The ones that were on-topic got the job done, so I second your recommendation. – Gerry Myerson May 21 '12 at 4:44
You can have a look at the proof of Theorem 5.2.3, p.57 in the book Ireland, Rosen: A Classical Introduction to Modern Number Theory, GTM 84. – Martin Sleziak May 21 '12 at 6:30

## 1 Answer

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.

-