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

Question

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.

Answer 1

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$.

Answer 2

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.

Answer 3

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)$