NTIC Square Roots

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 to finding solutions to \(x^2\equiv n\text{ (mod }p)\text{,}\) though since \(f'(x)=2x\) our version of Hensel's Lemma is not strong enough to fully reduce when \(p=2\text{.}\) We will ignore this caveat and focus on solving for square roots modulo a prime.

We have already done some of this! 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.

Fact 16.1.1.

The congruence \(x^2\equiv 1\) (mod \(p\)), for \(p\) prime, always has the solution(s) \(x\equiv \pm 1\text{.}\) So if \(p=2\) there is one solution, and otherwise \(1\) has two square roots modulo \(p\text{.}\)

Fact 16.1.2.

The congruence \(x^2\equiv -1\) (mod \(p\)), for \(p\) prime, does not always have solutions. It does precisely when \(p=2\) (where \(x\equiv 1\)) and when \(p\equiv 1\) (mod \(4\)), which has the two solutions

\begin{equation*} x\equiv \pm \left(\frac{p-1}{2}\right)! \end{equation*}

where again the exclamation point here indicates the factorial.

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.

Algorithm 16.1.5.

To solve a polynomial modulo a given modulus \(n\text{,}\) the following information suffices, granted the technical condition for the first bullet that \(\gcd(p,f'(x))=1\) for a solution \(x\) modulo a prime factor¹ \(p\mid n\text{.}\)

If we can solve, for a given prime \(p\text{,}\)

\begin{equation*} f(x)\equiv 0\text{ (mod }p)\text{,} \end{equation*}

we can solve

\begin{equation*} f(x)\equiv 0\text{ (mod }p^e)\text{.} \end{equation*}
If we can solve, for coprime integers \(p\) and \(q\text{,}\) \(f(x)\equiv 0\text{ (mod }p)\text{ and }(q)\text{,}\) then we can solve

\begin{equation*} f(x)\equiv 0\text{ (mod }pq)\text{.} \end{equation*}

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 a solution modulo \(p\text{.}\)

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{;}\) else see [E.2.1, Theorem 7.14, Examples 7.13-14].