Given a congruence equation of the form
x2 ≡ a (mod m)
how would you go about solving it? 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.
Relatively prime a and m
Throughout these notes we will assume a and m have no factors in common. Why? Because if a = da′ and m = dm′, then we can solve
x2 ≡ a′ (mod m′)
and multiply x by d to get a solution to the original equation.
Reduce general moduli to prime power moduli
The next step in the reduction to 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 = 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.)