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.
Best Answer
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.