# Quadratic residues mod $n$ of $n-1$

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.

• – lab bhattacharjee May 19 '13 at 6:31
• You're asking for $-1$ to be a quadratic residue. This is discussed in any text that does quadratic residues. – Gerry Myerson May 19 '13 at 6:32

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\,$.
• What's $p=2$? Chopped liver? – Gerry Myerson May 19 '13 at 6:46