Consider the ring \(\mathbb{Z}/ n\) of integers modulo some number \(n\). Does there exist a square root of \(-1\) in \(\mathbb{Z}/ n\)? Equivalently, does there exist an integer \(x\) such that \(n\) divides \(x^2 + 1\)?
For an example, note that \(2^2 \equiv -1\) modulo \(5\). On the other hand, there is no number which squares to \(-1\) modulo \(7\).
Modulo powers of 2
First, observe that in the case \(n=2\) we actually have \(1 \equiv -1\) so that a (in this case unique) square root of \(-1\) trivially exists. Next, consider the case \(n = 2^{\alpha}\). Note that \(x^2 + 1\) modulo \(4\) is either \(1\) or \(2\) depending on whether \(x\) is even or odd. In any case, \(x^2 + 1\) is not divisible by \(4\) which shows that there are no square roots of \(-1\) in the case \(n = 2^{\alpha}\) when \(\alpha > 1\).
Modulo primes
The following is a standard theorem that answers our question for \(n\) an odd prime.
Theorem: Let \(p\) be an odd prime. The equation \(x^2 = -1\) has a solution in \(\mathbb{Z}/ p\) if and only if \(p \equiv 1\) modulo \(4\), in which case there are exactly two solutions.
Proof: First, we are going to show that \(-1\) is the unique element of order \(2\) in \((\mathbb{Z}/ p)^{\times}\). Let \(x\) be such an element of order \(2\). Then \(p\) divides \(x^2 - 1\) and hence \(p\) divides either \(x-1\) or \(x+1\) which implies that \(x = 1\) or \(x = -1\). Being of order \(2\), \(x = -1\). Alternatively, one could just note that \(x^2 - 1\) can have at most two roots in the field \(\mathbb{Z}/ p\).
Therefore, an element x of \(\mathbb{Z}/ p\) satisfies \(x^2 = -1\) if and only if it is of order \(4\) in \((\mathbb{Z}/ p)^{\times}\). Assume that we have such an element of order \(4\). This implies that \(4\) divides \(| (\mathbb{Z}/ p)^{\times} | = p - 1\). The claimed necessity of \(p \equiv 1\) modulo \(4\) follows.
Now, suppose \(p \equiv 1\) modulo \(4\). Consider the group $$ G = (\mathbb{Z}/ p)^{\times} /\{\pm 1\}. $$ Its order \(|G| = (p - 1) / 2\) is even which implies that \(G\) contains at least one element \(g\) of order \(2\). Let \(x\) be in the preimage of \(g\) under the quotient map. The order of \(x\) can only be \(2\) or \(4\). If it were \(2\) then \(x = -1\) which would imply the contradiction that \(g = 1\). Consequently, \(x\) is of order \(4\) and \(\pm x\) (which are distinct) are our seeked solutions. Since \(\mathbb{Z}/ p\) is a field there can't be further solutions.
Modulo prime powers
Examining the previous proof we can generalize to the case of prime powers \(n = p^{\alpha}\).
Theorem: Let \(p\) be an odd prime. The equation \(x^2 = -1\) has a solution in \(\mathbb{Z}/ p^{\alpha}\) if and only if \(p \equiv 1\) modulo \(4\), in which case there are exactly two solutions.
Proof: Again, we claim that \(-1\) is the unique element of order \(2\) in \((\mathbb{Z}/ p^{\alpha})^{\times}\). If \(x\) is such an element then \(p^{\alpha}\) divides \(x^2 - 1\) and hence \(p^{\alpha}\) divides either \(x - 1\) or \(x + 1\) (note that \(p\) can't divide both \(x - 1\) and \(x + 1\)). We conclude \(x = -1\).
Therefore, an element \(x\) of \(\mathbb{Z}/ p^{\alpha}\) satisfies \(x^2 = -1\) if and only if it is of order \(4\) in \((\mathbb{Z}/ p^{\alpha})^{\times}\). Assume that we have such an element of order \(4\). This implies that \(4\) divides \(| (\mathbb{Z}/ p^{\alpha})^{\times} | = p^{\alpha - 1} (p - 1)\). The claimed necessity of \(p \equiv 1\) modulo \(4\) again follows.
Now, suppose \(p \equiv 1\) modulo \(4\). Consider the group $$ G = (\mathbb{Z}/ p^{\alpha})^{\times} /\{\pm 1\}. $$ Its order \(|G| = p^{\alpha - 1} (p - 1) / 2\) is even which implies that \(G\) contains at least one element \(g\) of order \(2\). Let \(x\) be in the preimage of \(g\) under the quotient map. The order of \(x\) can only be \(2\) or \(4\). If it were \(2\) then \(x = -1\) which would imply the contradiction \(g=1\). Consequently, \(x\) is of order \(4\) and \(\pm x\) (which are distinct) are two solutions. To see that there are no further elements of order \(4\), suppose \(x\) and \(y\) are of order \(4\). It follows from \(x^2 = y^2 = -1\) that \((x y)^2 = 1\), and hence \(x y = \pm 1\). This implies \(y = \pm x\).
The general case
We are now able to prove the following theorem.
Theorem: The equation \(x^2 = -1\) has a solution in \(\mathbb{Z}/ n\) if and only if \(n\) decomposes as $$ n = 2^{\varepsilon} p_1 \cdots p_r $$ where \(\varepsilon \in \{0, 1\}\) and the \(p_j\) are primes satisfying \(p_j \equiv 1\) modulo \(4\). In this case, there are exactly \(2^s\) solutions where \(s\) is the number of distinct primes among the \(p_j\).
Proof: This is an immediate consequence of our previous discussion, and the Chinese Remainder Theorem. If \(n = n_1 n_2\) for relatively prime \(n_1\) and \(n_2\), then n divides \(x^2 + 1\) if and only if both \(n_1\) and \(n_2\) divide \(x^2 + 1\). We conclude that \(n\) is of the claimed form in order for a solution of \(x^2 = -1\) to exist.
On the other hand, given that \(n = 2^{\varepsilon} p_1^{\alpha_1} \cdots p_s^{\alpha_s}\) for distinct primes \(p_j\) such that \(p_j \equiv 1\) modulo \(4\), we find exactly two solutions for each of the \(s\) equations $$ x^2 \equiv -1 \hspace{1em} \operatorname{mod} p_j^{\alpha_j} . $$ Using the isomorphism given by the Chinese Remainder Theorem, these combine to exactly \(2^s\) solutions of \(x^2 \equiv -1\) modulo \(n\).