Given a congruence equation of the form

*x*^{2} ≡ *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

*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.

## 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

*x*^{2} ≡ *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* = *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 ^{n}* 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* 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} = *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

_{k}2 *x _{k} y_{k}* ≡ 1 (mod

*p*).

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

Thus *p ^{n}* 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, 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 ^{n}*. Therefore

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

or

*x* ≡ –*y* (mod *p ^{n}*).

So if *a* has any square root modulo *p ^{n}* — 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.)