On modular roots of $-1$? Given $n\in\Bbb N$ what is the best method to find if there is an $x\in\Bbb Z_n$ such that $x^2\equiv-1\bmod n$?
I mean supposing we have $x^2\equiv-1\mod p$ how to find that $x$ when $p$ is a prime?
 A: When $p$ is an odd prime congruent to 1 modulo 4, $$ \left( \frac{p-1}{2} \right)! $$ is a solution to $x^2 \equiv -1 \mod p$. However this congruence is not solvable when $p$ is congruent to 3 modulo 4.
A: If $n = qr$ for relatively prime $q,r>1$, then we can split this up into 
$$
x^2 \equiv -1 \pmod{q}\\
x^2 \equiv -1 \pmod r
$$
Thus, it suffices to handle the case in which $n = p^k$ for some prime $p$.
If $n = p > 2$, then it is well known that $x^2 \equiv -1$ has a solution if and only if $p \equiv 1 \pmod 4$.  Of course, if $n = 2$, then $1^2 \equiv -1$.  I don't know of any other results here.
However, we could certainly check the $p^k$ case exhaustively.
EDIT: Or, apparently we can find the solutions for $p^k$ using Hensel's lemma.
A: An alternate method to the one suggested by Omnomnomnom is the following:
First, as Omnomnomnom pointed, it suffices to solve the problem for the case $n=p^k$.
Now, and here is where this alternate method can work or fail badly, the theory tells us that there exists primitive roots $\pmod{p^k}$. If you know a primitive root $b\pmod{p^k}$, then 
$$ord(b)=p^{k-1}(p-1)$$
Let $m=p^{k-1}\frac{p-1}{2}$. Then $b^{m}$ is a root of 
$$y^2=1 \pmod{p^k}$$
and $b \neq 1 \pmod{p^k}$. As long as $p \neq 2$, it is easy to prove that $y^2=1 \pmod{p^k}$ only has solutions $\pm1$. Thus 
$$b^m =-1 \pmod{p^k}$$
Therefore, the equation you are trying to solve is
$$x^2 = b^m \pmod{p^k}$$
and since $m$ is even (this is where we use $p =1 \pmod{4}$, and this is why this is necessary) we have the obvious solutions
$$x= \pm b^\frac{m}{2}$$
Conclusion: If $b$ is a primitive root, then 
$$x= \pm b^{\frac{p-1}{4}p^{k-1}}$$
A: You can use the Chinese remainder theorem: if $n=2^rp_1^{r_1}\dots p_l^{r_l}$, then $x^2\equiv -1\mod n$ if and only if
$$\begin{cases}x^2\equiv -1\mod 2^r\\
x^2\equiv -1\mod p_1^{r_1}\\
\vdots\\
x^2\equiv -1\mod p_l^{r_l}
\end{cases}$$
Now we know there are solutions $\bmod 2$ or $4$, but not  $\mod 2^r \;(r\ge3$).
Next Hensel's lemma asserts that $x^2\equiv -1\mod p_i^{r_i}$ has solutions if and only if it has $\bmod p_i$.
Last, $x^2\equiv -1\mod p_i$ has solutions if and only if $p_i\equiv 1\mod4$ by the first supplementary law of quadratic reciprocity.
Summing up, the equation $x^2\equiv-1$ has solutions if and only if $n $ has no odd prime factor  congruent to $3$ mod $4$ and, if $n$ is even, it is divisible at most by $2$ or $4$. 
