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.
 A: 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.
A: 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$.
A: This statement is equivalent to asking when a prime $p$ divides $n^2+1=(n+i)(n-i)$. Thus in $\mathbb{Z}[i]$, we have 
$$kp=(n+i)(n-i)$$
If $p$ is also a Gaussian prime, then $p$ divides both $n+i$ and $n-i$ which happens only if $p=2$ which is not a Gaussian prime. Thus, $p$ is not a Gaussian prime. Now, we use the following chain of reasoning:
$$p \text{ is Gaussian prime} \Leftrightarrow \mathbb Z_p[i] \text{is a field}$$
$$\Leftrightarrow  \mathbb Z_p[x]/(x^2+1) \text{ is a field}$$
$$\Leftrightarrow x^2+1 \text{ is prime in } \mathbb Z_p[x] $$
$$\Leftrightarrow \sqrt{-1} \text{ does not exist in } \mathbb Z_p$$
The last condition is satisfied if and only is $p\equiv 3( \text{mod }p)$
