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
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.
Fact16.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{.}\)
Fact16.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
where again the exclamation point here indicates the factorial.
Subsection16.1.2Finding 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.
Example16.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
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!)
Example16.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:
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.
Algorithm16.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 2 \(p\mid n\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{,}\) 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{.}\)