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

  • 1
    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).$$2012-05-20
  • 0
    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!2012-05-20
  • 2
    **Hint** See this long interesting 1998/5/13 sci.math thread [square in every $\mathbb Z/m$ implies square?](http://groups.google.com/group/sci.math/browse_frm/thread/78f034b9edcee53b/51bec8b9198fd868)2012-05-20
  • 0
    @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.2012-05-21
  • 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.