# Is every integer a quadratic residue mod some p?

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

-

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 '14 at 17:42
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