Section16.1Square Roots
To use the quadratic formula, one needs square roots in the real numbers. So too, our first task for modular arithmetic will be solving \[x^2\equiv n\text{ mod }(p)\, ,\] or finding square roots modulo \(p\) a prime.
We have already done some of this, indeed!
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 \[x\equiv \pm \left(\frac{p-1}{2}\right)!\, .\]Subsection16.1.1Finding more answers
What about finding out when \(-1\) has a square root for non-prime moduli? We can ask Sage about this:
But we actually can get a complete answer to this, using Hensel's Lemma and the Chinese Remainder Theorem. Namely:
- If we can solve, for a given prime \(p\), \[f(x)\equiv 0\text{ mod }(p)\; ,\] then we can solve \[f(x)\equiv 0\text{ mod }(p^e)\; .\] (There is a technical condition that \(p\nmid f'(x_0)\) for any original solution \(x_0\).)
- If we can solve, for coprime integers \(p\) and \(q\), \(f(x)\equiv 0\text{ mod }(p)\text{ and }(q)\; ,\) then we can solve \[f(x)\equiv 0\text{ mod }(pq)\; .\]
Example16.1.3Prime power modulus
For instance, let's go from \(p\) to \(p^2\). 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 \[\frac{2^2+1}{5}+k(2\cdot 2)\equiv 0\text{ mod }(5)\] 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.4Composite 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)
- \(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)\)