Square roots of minus one in modular arithmetic

Consider the ring of integers modulo some number n. Does there exist a square root of -1 in ? Equivalently, does there exist an integer x such that n divides x² + 1?

For an example, note that 2² ≡ -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 ≡ -1 so that a (in this case unique) square root of -1 trivially exists. Next, consider the case n = 2^α. Note that x² + 1 modulo 4 is either 1 or 2 depending on whether x is even or odd. In any case, x² + 1 is not divisible by 4 which shows that there are no square roots of -1 in the case n = 2^α when α > 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² = -1 has a solution in if and only if p ≡ 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 . Let x be such an element of order 2. Then p divides x² - 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² - 1 can have at most two roots in the field .

Therefore, an element x of satisfies x² = -1 if and only if it is of order 4 in . Assume that we have such an element of order 4. This implies that 4 divides . The claimed necessity of p ≡ 1 modulo 4 follows.

Now, suppose p ≡ 1 modulo 4. Consider the group

Its order 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 ± x (which are distinct) are our seeked solutions. Since 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^α.

Theorem: Let p be an odd prime. The equation x² = -1 has a solution in if and only if p ≡ 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 . If x is such an element then p^α divides x² - 1 and hence p^α 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 satisfies x² = -1 if and only if it is of order 4 in . Assume that we have such an element of order 4. This implies that 4 divides . The claimed necessity of p ≡ 1 modulo 4 again follows.

Now, suppose p ≡ 1 modulo 4. Consider the group

Its order 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 ± 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² = y² = -1 that (x y)² = 1, and hence x y = ± 1. This implies y = ± x.

The general case

We are now able to prove the following theorem.

Theorem: The equation x² = -1 has a solution in if and only if n decomposes as

where ε ∈ {0, 1} and the p_j are primes satisfying p_j ≡ 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₁ n₂ for relatively prime n₁ and n₂, then n divides x² + 1 if and only if both n₁ and n₂ divide x² + 1. We conclude that n is of the claimed form in order for a solution of x² = -1 to exist.

On the other hand, given that for distinct primes p_j such that p_j ≡ 1 modulo 4, we find exactly two solutions for each of the s equations

Using the isomorphism given by the Chinese Remainder Theorem, these combine to exactly 2^s solutions of x² ≡ -1 modulo n.