How do you solve congruences of the form x 2 ≡ 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 2 ≡ 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 1 e 1 p 2 e 2 … pr er . If the congruence x 2 ≡ a (mod m) has a solution, that solution is necessarily a solution to each of the prime power congruences x 2 ≡ a (mod pi ei ). 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 2 ≡ a (mod pn ) to have a solution is for x 2 ≡ a (mod p) to have a solution. (To see this, note that if x 2 – a is divisible by pn 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 2 ≡ a (mod 2) has a solution, namely x ≡ 1 (mod 2).

Next, x 2 ≡ 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 2 ≡ a (mod 2 n ) has four unique solutions if a ≡ 1 (mod 8) and no solutions otherwise.

If a ≡ 1 (mod 8) then x 2 ≡ a (mod 8) has four solutions: 1, 3, 5, and 7. The solutions to x 2 ≡ a (mod 2 n ) 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 xk 2 ≡ a (mod 2 k ) for k ≥ 3. By definition, this means x 2 – a is divisible by 2 k . If (x 2 – a)/2 k is odd, let i = 1. Otherwise let i = 0. Then x k+1 defined byxk + i 2 k-1 is a solution to x k+1 2 ≡ 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 2 ≡ a (mod p) and produce solutions to x 2 ≡ a (mod pn ) for n = 2, 3, 4, etc.

Suppose xk is a solution to x 2 ≡ a (mod pk ) for some k ≥ 1. Let yk be a solution to 2 xk yk ≡ 1 (mod pk ). Then x k+1 = x k – (x k 2 – a)yk is a solution to x 2 ≡ a (mod p k+1).

The procedure above shows how to construct one solution to x 2 ≡ a (mod pn ) 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 2 = y 2 ≡ a (mod pn ) where p is an odd prime and a is relatively prime to p. Then x 2 – y 2 ≡ (x – y)(x + y) ≡ 0 (mod pn ). Thus pn 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 2 ≡ a (mod pn ), and so x 2 = k pn + a for some k. If p divided x, then p would divide x 2, and therefore p would divide a, and a would not be relatively prime to pn . Therefore p divides neither x nor y. It follows that p either divides (x+y) or (x–y) but not both. Since pn divides (x+y)(x–y), it only divides one of (x+y) and (x–y). Therefore, either x ≡ y (mod pn ) or x ≡ –y (mod pn ). So if a has any square root modulo pn — 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 2 ≡ 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 2 ≡ 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 p ≡ 3 (mod 4) then a (p+1)/4 is a solution to x 2 ≡ 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.)

Click to learn more about math and computing consulting