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

Is every integer (say $d$) a quadratic residue mod some prime number $p$?

share|cite|improve this question
up vote 15 down vote accepted

Yes. Let $p$ be any prime divisor of $d-1$ or of $d-4$ or of $d-9$ or ...

share|cite|improve this answer
What if $d = 2$? – Mario Carneiro Apr 28 '14 at 17:42
Does 4≡0 mod 2 count? (If so, I would think the proof could be simplified to "let p be any prime divisor of d".) If not, there's always 9≡2 mod 7. – Brilliand Apr 28 '14 at 18:11
So what happens when the condition is tightened to require $p>d$? – jpvee Apr 29 '14 at 11:35
@jpvee Instead of considereing all $d-k^2$ as in the answer above, elminate certain residue classes. Namely, for each prime $q\le d$, either $q\mid d$ and then $q\not\mid d-k^2$ for all $k\equiv 1\pmod q$; or $q\not\mid d$ and then $q\not\mid d-k^2$ for all $k\equiv 0\pmod q$. Now use the chinese remainder theorem to find $k$ that obeys these finitely many modular constraints and such that $d-k^2\ne\pm1$. Let $p$ be a prime divisor of $d-k^2$. By construction, $p>d$. – Hagen von Eitzen May 23 '14 at 14:44
But, $d-k^2\le d,$ so $p\not\gt d$? Perhaps we can consider $n^2d-k^2$ and the prime divisors of $n^2d-k^2$ which are prime to $n$ instead? – awllower Nov 14 '14 at 5:45

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.