While investigating something about square numbers, I started to wonder which numbers $n$ have quadratic residues of $n-1$. Obviously all $n$ of the form $m^2+1$ will work. But there are other numbers such as $13$, is there a pattern to them? Any insights on this would be great.


In very short:

The equation $\,x^2=-1\pmod p\,,\;p\,$ a prime, has solution iff $\,p=1\pmod 4\,$ or $\,p=2\,$ (this is already a very nice exercise), and from here, with the prime factorization of $\,n\in\Bbb N\,$ , you get the corresponding condition for $\,x^2=-1\pmod m\,$.

  • $\begingroup$ What's $p=2$? Chopped liver? $\endgroup$ – Gerry Myerson May 19 '13 at 6:46
  • $\begingroup$ Oops...that's what happens to even primes. Corrected and thanks. $\endgroup$ – DonAntonio May 19 '13 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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