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 solveFact 16.1.1.
The congruence
Fact 16.1.2.
The congruence
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 ofxxxxxxxxxx
var('x')
def _(n=50):
for i in [2..n]:
sols = [sol[0] for sol in solve_mod([x^2==-1],i)]
l = len(sols)
if l!=0:
pretty_print(html("$x^2=-1\\text{ (mod }%s)$ has $%s$ solutions, $%s$"%(i,l,sols)))
Example 16.1.3. Prime power modulus.
For instance, let's go from
Remembering that
which is
(Notice that
Example 16.1.4. Composite moduli.
Suppose I want solutions to
But if I am looking (mod
(mod ) (mod )
We combine them thus:
And that also is consistent with the computations in the Sage interact above!
Algorithm 16.1.5.
To solve a polynomial modulo a given modulus
-
If we can solve, for a given prime
we can solve
-
If we can solve, for coprime integers
and then we can solve