How do you solve congruences of the form x2 ≡ 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 x2 ≡ 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 = p1e1 p2e2 … prer. If the congruence x2 ≡ a (mod m) has a solution, that solution is necessarily a solution to each of the prime power congruences x2 ≡ a (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 x2 ≡ a (mod pn) to have a solution is for x2 ≡ a (mod p) to have a solution. (To see this, note that if x2 – 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, x2 ≡ a (mod 2) has a solution, namely x ≡ 1 (mod 2).
Next, x2 ≡ 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, x2 ≡ a (mod 2n) has four unique solutions if a ≡ 1 (mod 8) and no solutions otherwise.
If a ≡ 1 (mod 8) then x2 ≡ a (mod 8) has four solutions: 1, 3, 5, and 7. The solutions to x2 ≡ a (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 xk2 ≡ a (mod 2k) for k ≥ 3. By definition, this means x2 – a is divisible by 2k. If (x2 – a)/2k is odd, let i = 1. Otherwise let i = 0. Then xk+1 defined by xk + i 2k-1 is a solution to xk+12 ≡ a (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 x2 ≡ a (mod p) and produce solutions to x2 ≡ a (mod pn) for n = 2, 3, 4, etc.
Suppose xk is a solution to x2 ≡ a (mod pk) for some k ≥ 1. Let yk be a solution to 2 xk yk ≡ 1 (mod pk). Then xk+1 = xk – (xk2 – a)yk is a solution to x2 ≡ a (mod pk+1).
The procedure above shows how to construct one solution to x2 ≡ 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 x2 = y2 ≡ a (mod pn) where p is an odd prime and a is relatively prime to p. Then x2 – y2 ≡ (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 x2 ≡ a (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 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 x2 ≡ 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 x2 ≡ 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 x2 ≡ 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.)