Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 11 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

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.