Skip to main content
Logo image

Section 16.1 Square Roots

Subsection 16.1.1 Recalling existing answers

To use the quadratic formula in full generality, one needs to know whether one can take square roots (for example, if they are complex, you won’t have a real solution). So too, our first task for modular arithmetic will be finding such square roots.
Given our work in Chapter 7, e.g. Fact 7.2.2, it should be sufficient to solve
\begin{equation*} x^2\equiv n\text{ (mod }p^e)\text{,} \end{equation*}
finding square roots modulo \(p^e\) where \(p\) is prime. In most cases, we can proceed as in Examples 7.2.5 and 7.2.6 to reduce our problem to finding solutions to \(x^2\equiv n\text{ (mod }p)\) and then lifting. Since \(f'(x)=2x\text{,}\) Hensel’s Lemma is not strong enough to guarantee we can always do that when \(p=2\text{,}\) but one can use Remark 7.2.7 to analyze this case as well.
In this chapter we will mostly ignore this caveat about powers, and focus on solving for square roots modulo a prime. In fact, we have already solved some simple cases! We restate here a fact in the proof of Theorem 12.3.2 and the combination of Fact 13.3.2 and Lemma 13.3.3.

Subsection 16.1.2 Finding more answers

We know the full answer (any modulus) for square roots of \(+1\) from Fact 7.3.1. What about finding out when \(-1\) has a square root for non-prime moduli? We can ask Sage about this:
Let’s see a few examples of how to be more systematic about this.

Example 16.1.3. Prime power modulus.

For instance, let’s go from \(p\) to \(p^2\) by trying a bit of Example 7.2.5 from earlier. Here, \(f(x)=x^2+1\) is what we want a solution for. If we are looking (mod \(25\)), then we already know that (mod \(5\)) we have \(x\equiv 2\) as a solution. Then a solution (mod \(25\)) will look like \(2+k(5)\) (again recall Example 7.2.5).
Remembering that \(f'(x)=2x\text{,}\) in fact it will satisfy
\begin{equation*} \frac{2^2+1}{5}+k(2\cdot 2)\equiv 0\text{ (mod }5) \end{equation*}
which is \(1+4k\equiv 0\text{,}\) which has solution \(k\equiv 1\text{;}\) hence a solution (mod \(25\)) should be \(2+1(5)\equiv 7\text{.}\) And indeed \(7^2+1=50\) is divisible by \(25\) as expected!
(Notice that \(5\nmid f'(2)=4\text{,}\) so the technical condition is granted; otherwise we’d have \(1\equiv 0\) to solve!)

Example 16.1.4. Composite moduli.

Suppose I want solutions to \(x^2\equiv -1\) (mod \(14\)). I should immediately note that although \(x^2\equiv -1\) (mod \(2\)) has a solution, \(x^2\equiv -1\) (mod \(7\)) does not (it’s a prime of the form \(4k+3\)) so there will be no solutions modulo \(14\) either.
But if I am looking (mod \(65\)), since \(65=5\cdot 13\) and \(x^2\equiv -1\) has solutions both (mod \(5\)) and (mod \(13\)), I can use the Chinese Remainder Theorem to combine them:
  • \(x\equiv 2\) (mod \(5\))
  • \(x\equiv 5\) (mod \(13\))
We combine them thus:
\begin{equation*} x\equiv 2\cdot 13\cdot (13^{-1}\text{ (mod }5))+5\cdot 5\cdot (5^{-1}\text{ (mod }13)) \end{equation*}
\begin{equation*} \equiv 26\cdot 2+25\cdot 8\equiv 252\equiv 57\text{ (mod }65) \end{equation*}
And that also is consistent with the computations in the Sage interact above!
As we can see, we can usually obtain a complete answer to this and similar questions by using Theorem 7.2.3 and Theorem 5.3.2.
Returning to square roots, it should be clear that, as far as just determining whether a solution exists, all we need to examine is prime moduli and powers of two. Everything else is taken care of by previous work.
To avoid the complication of powers of two, and because of a similar complication in completing the square in Algorithm 16.2.4, in the rest of this chapter and the next we will focus on the case of odd moduli. It can be a useful classroom exercise to explore both when solutions exist and the actual square roots modulo \(2^e\text{,}\) for which see Exercise 16.8.17; for full details see [E.2.1, Theorem 7.14, Examples 7.13-14].
Why not prime power factor? Because in the construction of Theorem 7.2.3 solutions modulo \(p^e\) are also solutions modulo \(p\text{.}\) So if \(p\) divides \(f'(x_e)\) for a solution \(x_e\text{,}\) it will already divide \(f'(x)\) for some solution modulo \(p\text{.}\)