# Solving quadratic congruences

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^{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^{k}) for k ≥ 3. By definition, this
means x^{2} - a is divisible by 2^{k}. If (x^{2} - a)/2^{k} is odd, let 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^{k}) for some k ≥ 1.
Let y_{k} be a solution to 2 x_{k} y_{k} ≡ 1 (mod p).
Then x_{k+1} = x_{k} - (x_{k}^{2} - a)y_{k} is
a solution to 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, 2x and -2y.
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^{n} divides (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 a ≡ 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.)