Which primes $p$ satisfy $n^2 \equiv -1 \mod p$ for a perfect square $n^2$? I am trying to solve a homework exercise in elementary number theory:

Which primes $p$ satisfy $n^2 \equiv -1 \mod p$ for a perfect square $n^2$? 

After looking at the case $p=5$, I saw that $3^2 \equiv 4 \mod 5$, but $p=2^2+1$, I thought that maybe the answer would be primes $p$ such that $p=m^2+1$ for some $m$. Certainly this would imply that there is an $n$ so that $p \mid n^2+1$ (in particular $n=m$).
Unfortunately, $n=13$ doesn't satisfy that condition. However, weakening it to $p\mid n^2+1$ for some $n$ is just the statement of the problem. I don't want to answer "the congruence is true for primes for which it is true." So I am back to square one.

The answer is exactly the primes which are congruent to $1,2 \bmod 4$.
The only prime congruent to $2 \pmod 4$ is $2$, so assume $p$ is odd for the rest of the answer.
The result follows pretty straightforwardly once we establish a basic result about the ring $\mathbb{Z}/p\mathbb{Z}$.
Result: There exists some $g$ such that every nonzero element $c$ in $\mathbb{Z}/p\mathbb{Z}$ can be expressed as $c= g^n$ for some $n$. (The unit group is cyclic.)
Back to the problem, we are essentially solving $x^2\equiv -1\bmod p$. Write $x$ as $g^n$ for some generator $g$, so we have $g^{2n}=-1\bmod p$, or equivalently $$g^{2n}=g^{\frac{p-1}{2}}\pmod p.$$ So $2n=\frac{p-1}{2}\bmod p-1$. If $p\equiv 1\bmod 4$, there is clearly a solution, and if $p\equiv 3\bmod 4$, this has no solutions. (Verify this.)
In general, the law of quadratic reciprocity provides a simple criterion for determining whether or not a square root exists modulo a prime.
