Solving quadratic congruences

How do you solve congruences of the form x2a (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 x2a (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 = p1e1 p2e2prer. If the congruence x2a (mod m) has a solution, that solution is necessarily a solution to each of the prime power congruences x2a (mod piei). 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 x2a (mod pn) to have a solution is for x2a (mod p) to have a solution. (To see this, note that if x2a 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, x2a (mod 2) has a solution, namely x ≡ 1 (mod 2).

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

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

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

The procedure above shows how to construct one solution to x2a (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 x2 = y2 a (mod pn) where p is an odd prime and a is relatively prime to p. Then x2y2 ≡ (xy)(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 x2a (mod pn), and so x2 = k pn + a for some k. If p divided x, then p would divide x2, 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 xy (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 x2a (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 x2a (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 x2a (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.)