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.

Hint:
If $n^2 \equiv -1$, then $n^4 \equiv 1$.
Fermat's theorem gives $n^{p-1} \equiv 1$.
Therefore, $n^d \equiv 1$, where $d=\gcd(4,p-1)$.
Now consider the possible cases $d=1,2,4$.
