Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!


share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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