# Is every integer a quadratic residue mod some p?

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

-

## 1 Answer

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

-
What if $d = 2$? –  Mario Carneiro Apr 28 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 at 18:11
So what happens when the condition is tightened to require $p>d$? –  jpvee Apr 29 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 at 14:44