3
$\begingroup$

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

  • 0
    You can have a look at the proof of Theorem 5.2.3, [p.57](http://books.google.com/books?id=jhAXHuP2y04C&pg=PA57#v=onepage&q&f=false) in the book Ireland, Rosen: A Classical Introduction to Modern Number Theory, GTM 84.2012-05-21

1 Answers 1

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.