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.
 A: 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.
A: 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.
