Fact16.1.1
The congruence \(x^2\equiv 1\) (mod \(p\)) always has two solutions, \(x\equiv \pm 1\). So \(1\) has two square roots modulo \(p\) (or one, if \(p=2\)).
Section16.1Square Roots¶ permalink
Subsection16.1.1Recalling existing answers¶ permalink
To use the quadratic formula, one needs square roots in the real numbers. 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)\, ,\end{equation*} finding square roots modulo \(p\) a prime.
We have already done some of this! We restate here a fact in the proof of Theorem 12.3.1 and the combination of Fact 13.3.2 and Lemma 13.3.3.
Fact16.1.2
The congruence \(x^2\equiv -1\) (mod \(p\)) does not always have solutions. It does when \(p=2\) or when \(p\equiv 1\) (mod \(4\)), and when it does there are two solutions, namely \begin{equation*}x\equiv \pm \left(\frac{p-1}{2}\right)!\, .\end{equation*}
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:
But recall that we actually can get a complete answer to this and similar questions by using Hensel's Lemma and the Chinese Remainder Theorem.
Algorithm16.1.3
To solve a polynomial modulo a given modulus, the following information suffices.
If we can solve, for a given prime \(p\), \begin{equation*}f(x)\equiv 0\text{ (mod }p)\; ,\end{equation*} then up to the technical condition about \(\gcd(p,f'(p^{e-1}))=1\) we can solve \begin{equation*}f(x)\equiv 0\text{ (mod }p^e)\; .\end{equation*}
If we can solve, for coprime integers \(p\) and \(q\), \(f(x)\equiv 0\text{ (mod }p)\text{ and }(q)\; ,\) then we can solve \begin{equation*}f(x)\equiv 0\text{ (mod }pq)\; .\end{equation*}
Example16.1.4Prime power modulus
For instance, let's go from \(p\) to \(p^2\) by trying a bit of Example 7.2.4 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)\) (review earlier where we did this), and, remembering that \(f'(x)=2x\), 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\), which has solution \(k\equiv 1\); hence a solution (mod \(25\)) should be \(2+1(5)\equiv 7\), and the computations above verify this!
(Notice that \(5\nmid f'(2)=4\), so the technical condition is granted; otherwise we'd have to solve \(1\equiv 0\)!)
Example16.1.5Composite moduli
Similarly, if 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 I can't use the CRT.
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 CRT to combine them:
\(x\equiv 2\) (mod \(5\))
\(x\equiv 5\) (mod \(13\))
So \(x\equiv 2\cdot 13\cdot (13^{-1}\text{ (mod }5))+5\cdot 5\cdot (5^{-1}\text{ (mod }13))\equiv 26\cdot 2+25\cdot 8\equiv 252\equiv 57\text{ (mod }65)\) And that also is consistent with the computations above!