Solving quadratic congruences

How do you solve congruences of the form x² ≡ a (mod m)? Said another way, how do you find square roots in modular arithmetic?

Every number theory book I've seen points out that the general problem of solving x² ≡ a (mod m) can be reduced to the solving the special case where m is a prime then spends most of the time studying this special case in detail. However, I haven't seen a book that is entirely clear on exactly how to reduce the general problem to the problem of prime moduli, or how you can unwind the reduction to produce a solution to the original problem. I will try to fill in the gaps here.

Throughout these notes we will assume m and a have no factors in common.

Reduce general moduli to prime power moduli

The first step in the reduction is clear. Factor the modulus m into prime powers: m = p₁^e₁ p₂^e₂ ... p_r^e_r. If the congruence x² ≡ a (mod m) has a solution, that solution is necessarily a solution to each of the prime power congruences x² ≡ a (mod p_i^e_i). Conversely, if you find solutions to each of the prime power congruences, you can use the Chinese Remainder Theorem to produce a solution to the original problem.

Reduce prime power moduli to prime moduli

This is the part that is often not presented clearly. Also, powers of 2 must be handled separately from powers of odd primes, and the former is sometimes neglected.

For any prime p, a necessary condition for x² ≡ a (mod pⁿ) to have a solution is for x² ≡ a (mod p) to have a solution. (To see this, note that if x² - a is divisible by pⁿ then it is certainly divisible by p.) Perhaps surprisingly, this is also a sufficient condition.

Powers of 2

Let a be an odd integer. (Since we are assuming m and a are relatively prime, if m has a power of 2 as a factor, a must be odd.)

First, x² ≡ a (mod 2) has a solution, namely x ≡ 1 (mod 2).

Next, x² ≡ a (mod 4) has a solution if and only if a ≡ 1 (mod 4), in which case the solutions are x ≡ 1 (mod 4) and x ≡ 3 (mod 4).

Finally, for n ≥ 3, x² ≡ a (mod 2ⁿ) has four unique solutions if a ≡ 1 (mod 8) and no solutions otherwise.

If a ≡ 1 (mod 8) then x² ≡ a (mod 8) has four solutions: 1, 3, 5, and 7. The solutions to x² ≡ a (mod 2ⁿ) for n > 3 can be found by the procedure below that starts with each of the solutions (mod 8) and produces solutions by induction for higher powers of 2.

Suppose x_k² ≡ a (mod 2^k) for k ≥ 3. By definition, this means x² - a is divisible by 2^k. If (x² - a)/2^k is odd, let i = 1. Otherwise let i = 0. Then x_k+1 defined by x_k + i 2^k-1 is a solution to x_k+1² ≡ a (mod 2^k+1).

Powers of odd primes

Let p be an odd prime and let a be any integer relatively prime to p. Then there is a procedure based on Hensel's Lemma that can take a solution to x² ≡ a (mod p) and produce solutions to x² ≡ a (mod pⁿ) for n = 2, 3, 4, etc.

Suppose x_k is a solution to x² ≡ a (mod p^k) for some k ≥ 1. Let y_k be a solution to 2 x_k y_k ≡ 1 (mod p). Then x_k+1 = x_k - (x_k² - a)y_k is a solution to x² ≡ a (mod p^k+1).

The procedure above shows how to construct one solution to x² ≡ a (mod pⁿ) but it does not tell us whether there are more solutions. Next we'll show that if we find a solution x, there is exactly one other solution, -x. (Thanks to Nemo for providing this proof.)

Suppose x² = y² ≡ a (mod pⁿ) where p is an odd prime and a is relatively prime to p. Then x² - y² ≡ (x - y)(x + y) ≡ 0 (mod pⁿ). Thus pⁿ divides the product (x+y)(x-y) and so p divides the product as well.

If p divided both x+y and x-y, then p would divide both their sum and their difference, 2x and -2y. Since p is an odd prime, p does not divide 2 and so p would divide both x and y. Now x² ≡ a (mod pⁿ), and so x² = k pⁿ + a for some k. If p divided x, then p would divide x², and therefore p would divide a, and a would not be relatively prime to pⁿ. Therefore p divides neither x nor y. It follows that p either divides (x+y) or (x-y) but not both. Since pⁿ divides (x+y)(x-y), it only divides one of (x+y) and (x-y). Therefore, either x ≡ y (mod pⁿ) or x ≡ -y (mod pⁿ). So if a has any square root modulo pⁿ — call it x — then it has exactly two roots: x and -x.

Odd prime moduli

We only consider odd primes here because the case p = 2 was handled above. Therefore we assume p is an odd prime in this section.

If x² ≡ a (mod p) has a solution, we say a is a "quadratic reside mod p." If this congruence has no solution, we say x is a "quadratic non-residue mod p."

The congruence x² ≡ a (mod p) either has no solutions or two solutions. If x is a solution, so is -x.

Euler's Criterion says that an odd integer a relatively prime to p is a quadratic residue (mod p) if and only if a^(p-1)/2 ≡ 1 (mod p). This fact is enough to settle the question of whether a is a quadratic residue. It could be used in a practical algorithm using fast exponentiation. However, there is an extensive and beautiful theory called "quadratic reciprocity" that studies this problem further and produces more efficient algorithms.

If a is a quadratic residue (mod p) and a ≡ 3 (mod 4) then a^(p+1)/4 is a solution to x² ≡ a (mod p). If a ≡ 1 (mod 4) there is no analogous formula. In that case, one may use the Tonelli-Shanks algorithm. (Thanks to Alasdair McAndrew for pointing out this algorithm.)