arminstraub.com

# Square roots of minus one in modular arithmetic

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