# Solving the congruence $x^2 \equiv 4 \mod 105$. Is there an alternative to using Chinese Remainder Theorem multiple times?

I'm trying to solve $$x^2 \equiv 4 \mod 105.$$

This is of course equivalent to $$(x+2)(x-2) \equiv 0 \mod 105$$

which is also equivalent to the system of congruences

$$(x+2)(x-2) \equiv 0 \mod 3$$ $$(x+2)(x-2) \equiv 0 \mod 5$$ $$(x+2)(x-2) \equiv 0 \mod 7$$

which have solutions of $$x \equiv 1\ \text{or}\ 2$$ $$x \equiv 2\ \text{or}\ 3,\ \text{and}$$ $$x \equiv 2\ \text{or}\ 5$$ respectively.

Now, I could in principle take each combination of {$1,2$}, {$2,3$}, and {$2,5$} and use the Chinese Remainder Theorem to solve each system, but that seems incredibly tedious.

Is there a simpler way?

I'll note that this is a homework question, so it seems likely that there's a trick. Unfortunately I can't spot one.

• no trick....................................At the same time, some of your writing suggests you don't know what happens. What are the values $\pmod {15},$ just combine results for $3,5$ before going on – Will Jagy Feb 9 '17 at 21:14
• I do understand that I can just use the values that I obtain $\mod 15$ and then solve the system involving those values and the values $\mod 7$. Is that what you're getting at? – Alex Feb 9 '17 at 21:19
• sure. How many values $\pmod {15},$ and what are they? – Will Jagy Feb 9 '17 at 21:21

There are a couple ways to optimize. First you need only compute half of the $8$ combinations since if $\,x\equiv (a,b,c)\bmod (7,5,3)\,$ then $\,-x\equiv (-a,-b,-c)\bmod (7,5,3).\$ Then use CRT to solve it for general $\,a,b,c\,$ to get $\,x\equiv 15a+21b-35c\,$ Use that to compute those $4$ values. It's very easy

e.g. note $\ x\equiv (2,\color{#0a0}{-2},\color{#c00}2)\equiv 15(2)+21(\color{#0a0}{-2})-35(\color{#c00}2)\equiv 23\pmod{105}$

Negating it $\ (-2,\color{#0a0}2,\color{#c00}{-2})\equiv -x\equiv -23\equiv 82\pmod{105}.\$ Of course $\pm(2,2,2)\equiv \pm2.\$

Do as above for $\,(-2,2,2),\ (2,2,-2)\$ to get the other$\,4\,$ solutions (a couple minutes work).

Remark  There are also other ways we can exploit the negation symmetry on the solution space, i.e. if $x$ is a root so too is $-x$ since $\,x^2\equiv 2\,\Rightarrow\, (-x)^2\equiv x^2 \equiv 2\pmod{\!105}.\,$ Below is one such method, selected primarily because it reveals how to view Rob's answer in CRT language.

By CCRT = Constant case CRT: $\,x\equiv (2,2,2)\pmod{\!7,5,3}\iff x\equiv 2\pmod{\!105}.$ Its negation is $\,(-2,-2,-2)\,$ corresponding to $\,-2\pmod{\!105}.\,$ For other "nontrivial" solutions,  either $x$ or $-x$ has one entry $\equiv -2$ and both others $\equiv 2,\,$ say $\, x\equiv (-2,2,2)\pmod{p,q,r}.\,$ Again by CCRT $\,x\equiv (2,2)\pmod{q,r}\iff x\equiv 2\pmod{qr}$ by $\,q,r\,$ coprime. So we reduce from $3$ to the $2$ congruences below. Solving them by Easy CRT, using $p$ coprime to $qr,\,$ we get

\quad\ \ \begin{align} x&\equiv -2\!\pmod p\\ x&\equiv\ \ \,2\!\pmod{qr}\end{align}\!\iff x\equiv 2\ +\ qr\left[\,\dfrac{-4}{qr}\ \bmod\ p\,\right]\pmod{pqr}\,

\qquad \qquad\qquad\qquad\! \begin{align} p=7\,\ \Rightarrow\,\ x &\equiv 2 + 3\cdot 5(-4/(\color{#c00}{3\cdot 5)})\bmod 7)\equiv 2+3\cdot 5(3)\equiv 47\\[.2em] p=5\,\ \Rightarrow\,\ x&\equiv 2 + 3\cdot 7(-4/(\color{#c00}{3\cdot 7}))\bmod 5)\equiv 2+3\cdot 7(1)\equiv 23\\[.2em] p=3\,\ \Rightarrow\,\ x&\equiv 2 + 5\cdot 7{(-4/\!\!\!\underbrace{(\color{#0a0}{5\cdot 7})}_{\large \equiv\ \color{#c00}{1}\ {\rm or}\ \color{#0a0}{-1}}}\!\!\!)\bmod 3)\equiv 2\color{}{ +}5\cdot 7(1)\equiv 37\\ \end{align}

We arranged the above to exploit easy inverses  (of $\,\color{#c00}{1}$ or $\color{#0a0}{-1})\,$ just as in the first solution (cf. my comment below). So $\,47,23,37\,$ and their negatives $\,58,82,68\,$ are all the nontrivial solutions.

The method in Rob's answer is essentially equivalent to the above (without the CRT language), except it doesn't take advantage of the easy inverses, instead solving the congruences by brute force (sometimes this may be quicker than general methods when the numbers are small enough).

There is also another CRT optimization used implicitly in Rob's answer. Namely a change of variables $\ y = x\!-\!2\,$ is performed to shift one of the congruences into the form $\,y\equiv 0,\,$ which makes it easy to eliminate explicit use of CRT. We show how this works for the prior congruences, using the mod Distributive Law $\,ca\bmod cn =\, c(a\bmod n)\quad\qquad$

$\qquad qr\mid x\!-\!2\,\ \Rightarrow\,\ x\!-\!2\bmod{pqr}\, =\, qr\!\!\!\!\!\!\overbrace{\left[\dfrac{x\!-\!2}{qr}\bmod p\right]}^{\large\quad\ \ x\ \equiv\ -2\pmod{p}\ \ \Rightarrow}\!\!\!\!\!\!\! =\, qr\left[\dfrac{-4}{qr}\bmod p\right]$

That's the same solution for $\,x\!-\!2\,$ that Easy CRT gave above. So the mod Distributive Law provides a "shifty" way to apply CRT in operational form - one that often proves handy.

• Thanks. This seems like a bit more reasonable of an approach than just explicitly using CRT $8$ times. It's not entirely clear to me why we have $x \equiv 15a+21b-35c$. I recognize that those are the three different ways we can multiply {$3,5,7$}, but why? – Alex Feb 10 '17 at 14:51
• @Alex It follows by applying the general CRT formula, namely \begin{align} x\ &\equiv\ (a,b,c)\!\!\pmod{7,5,3}\\[.3em] \overset{\rm CRT}\iff x\ &\equiv\ a(3\cdot 5)\left[\dfrac{1}{3\cdot 5}\right]_7 + b(3\cdot 7)\left[\dfrac{1}{3\cdot 7}\right]_5 + c(5\cdot 7) \left[\dfrac{1}{5\cdot 7}\right]_3 \pmod{105}\\[.3em] &\equiv \quad a\,(15)\,(1/1)_7\ \ +\ \ b\,(21)\,(1/1)_5\ \ +\ \ c\,(35)\,(1/(-1))_3\\[.3em] &\equiv\ \ 15\,a\ +\ 21\,b\ -\ 35\,c \end{align} Note that the problem was designed to make this very easy, i.e. all the inverses are inverses of $\pm1.$ $\quad$ – Bill Dubuque Feb 10 '17 at 15:42
• What you describe as a computation by "brute force" in my answer amounts to a quick pass over a list of $12$ natural numbers $n$ less than $100$ to decide whether $n\pm4$ is a multiple of one of $3$, $5$, $7$. You seem to be doing much more calculation than I did. – Rob Arthan Feb 10 '17 at 23:05
• @Rob First, "brute force" is a very common name for such exhaustive searches. It's not meant to denigrate such methods (which are often useful). Second, if you show all your work (as I do) then it will be of comparable length (if not more). Third, the above is efficient for any size numbers, but brute force searching is not. Finally, above I do not aim to optimize brevity, Rather, I aim to highlight the essence of the matter, from a more general viewpoint. – Bill Dubuque Feb 10 '17 at 23:14
• @BillDubuque: first: the essence of this problem to me is "how can a quadratic equation have more than two roots in a commutative ring?". Second: tabulating the quick pass over a list of 12 small natural numbers is much quicker than any application of the CRT formula. – Rob Arthan Feb 10 '17 at 23:26

Here's a method for avoiding CRT altogether (which comes from thinking about why there can be more than two roots to a quadratic in a commutative ring). If $x$ is any solution, we have $$(x - 2)(x + 2) \equiv 0 \bmod 105.$$ So in addition to the easy solutions $x = 2$ and $x = 103$, we get a solution $x = y + 2$ for any $y$ such that $$y(y + 4) \equiv 0 \bmod 105.$$ I.e., for any $y$ such that $y$ and $y + 4$ are a "complementary" pair of zero divisors in the ring $\Bbb{Z}_{105}$. Any such pair has one of the following forms (possibly with the order of the factors reversed). \begin{align*} 3m &\cdot 35n & \quad &\mbox{with 1 \le n \le 2}\\ 15m &\cdot 7n & \quad &\mbox{with 1 \le m \le 6}\\ 5m &\cdot 21n & \quad &\mbox{with 1 \le n \le 4} \end{align*} It doesn't take long to work through the $2+6+4$ possibilities for $y$ or $y + 4$ to get that $y(y+4)$ must be one of:

$$21 \cdot 25\\ 35 \cdot 39 \\ 45 \cdot 49\\ 56 \cdot 60\\ 66 \cdot 70\\ 80 \cdot 84$$

Giving 23, 37, 47, 58, 68 and 82 as the not-so-easy solutions.

• As someone currently taking a ring theory class, I think this solution is really neat. Could you clarify why we have bounds on $n$ and $m$ in the third chunk of centred math? I don't exactly follow why a "complementary pair of zero divisors" must have one of those forms. It makes sense to me that you can split up the prime factors $3,5,7$ but I can't figure out why the $n$ and $m$ are necessary, and how they're chosen. – Alex Feb 9 '17 at 22:56
• @Alex: I think you understand that to get a non-trivial solution to $ab=0$ in $\Bbb{Z}_{105}$, you need to split the prime factors of $105$ between $a$ and $b$. Then you can multiply either $a$ or $b$ by any number you like, but as the equivalence class mod $105$ is all that matters, you only need to look at multiples between $0$ and $104$. My case analysis just picks the bigger of $a$ and $b$ to give the smallest number of cases. Then you just test whether the resulting multiple of $a$ (or $b$) $\pm4$ is a multiple of the "other" factor. – Rob Arthan Feb 9 '17 at 23:09
• @Alex Though CRT is not explicitly used above, in fact the method is a special case of general CRT optimizations, as I describe in the Remark in my answer. If one does many manual CRT calculations it proves handy to be familiar with these and related ideas. – Bill Dubuque Feb 10 '17 at 22:32