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!


  • 1
    $\begingroup$ 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).$$ $\endgroup$ – Jyrki Lahtonen May 20 '12 at 16:31
  • $\begingroup$ 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! $\endgroup$ – Jyrki Lahtonen May 20 '12 at 16:46
  • 2
    $\begingroup$ Hint See this long interesting 1998/5/13 sci.math thread square in every $\mathbb Z/m$ implies square? $\endgroup$ – Bill Dubuque May 20 '12 at 16:54
  • $\begingroup$ @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. $\endgroup$ – Gerry Myerson May 21 '12 at 4:44
  • $\begingroup$ 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. $\endgroup$ – Martin Sleziak May 21 '12 at 6:30

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.