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}^{e1} *p*_{2}^{e2} … *p _{r}*

^{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

*p*

_{i}^{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 *p ^{n}*) 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

*p*then it is certainly divisible by

^{n}*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* x _{k}*

^{2}≡

*a*(mod 2

*) for*

^{k}*k*≥ 3. By definition, this means

*x*

^{2}–

*a*is divisible by 2

*. If (*

^{k}*x*

^{2}–

*a*)/2

*is odd, let*

^{k}*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}

^{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 *p ^{n}*) for

*n*= 2, 3, 4, etc.

Suppose *x _{k}* is a solution to

*x*

^{2}≡

*a*(mod

*p*) for some

^{k}*k*≥ 1. Let

*y*be a solution to 2

_{k}*x*≡ 1 (mod

_{k}y_{k}*p*). Then

^{k}*x*

_{k+1}=

*x*

_{k}– (

*x*

_{k}

^{2}–

*a*)

*y*is a solution to

_{k}*x*

^{2}≡

*a*(mod

*p*

^{k+1}).

The procedure above shows how to construct one solution to *x*^{2} ≡ *a* (mod *p ^{n}*) 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 *p ^{n}*) where

*p*is an odd prime and

*a*is relatively prime to

*p*. Then

*x*

^{2}–

*y*

^{2}≡ (

*x*–

*y*)(

*x*+

*y*) ≡ 0 (mod

*p*). Thus

^{n}*p*divides the product (

^{n}*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, 2*x* and -2*y*. 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 *p ^{n}*), and so

*x*

^{2}=

*k*

*p*+

^{n}*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

*p*. Therefore

^{n}*p*divides neither

*x*nor

*y*. It follows that

*p*either divides (

*x*+

*y*) or (

*x*–

*y*) but not both. Since

*p*divides (

^{n}*x*+

*y*)(

*x*–

*y*), it only divides one of (

*x*+

*y*) and (

*x*–

*y*). Therefore, either

*x*≡

*y*(mod

*p*) or

^{n}*x*≡ –

*y*(mod

*p*). So if

^{n}*a*has any square root modulo

*p*— call it

^{n}*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.)