I need help with this congruence. What will be the approach to the solution? (From George E. Andrews book)

Question

From the book Number Theory by George. E. Andrews page 52

$n^2 \equiv -1$ (mod $p$)

Where $p$ is a prime. Characterize the primes for which this congruence has a solution.

Answer 1

As you'll find later in the book this deals with quadratic residues. But to just get a heuristic feel for the problem, try it for different primes. e.g. $n^2\equiv -1 \pmod5$ has a solution $(n=2,3)$, and so does $n^2\equiv -1 \pmod{13}$ ($n=5,8)$, however no solutions exist for $3,11$ or $7$. What characterizes them?

Note that for every prime with a solution $\frac{p-1}2$ is even, or equivalently $$(-1)^{\frac{p-1}2}\equiv1 \pmod p$$ Has solutions precisely when $p$ satisfies $n^2\equiv -1 \pmod p$, or in other words when $-1$ is a quadratic residue mod $p$. You can see Andrews' full proof of this, known as Euler's Criterion, on page 116.