Finding the square root $s$ of 1293 modulo 3337. If $3337 = 47 \cdot 71$, how do you find the square root $s$ of $1293 \pmod { 3337}$ (where $0 < s < 3337$).
I understand that $m = 3337 = p \cdot q$ and  $p=47$ and $q=71$, but not sure where to go from here.
 A: Here is a neat way to find square roots for $3 \pmod 4$ primes. If we want the solution for $x^2 \equiv c \pmod p$, then by Fermat, $c \cdot c^{(p-1)/2} \equiv c \equiv (c^{(p+1)/4})^2$ so the solutions are $\pm c^{(p+1)/4}$. No such easy way exists for $1 \pmod 4$ primes I think. 
A: HINT:
If $\displaystyle x^2\equiv1293\pmod{47\cdot71}\implies x^2\equiv1293\pmod{47}\equiv24$
Now by trial, $\displaystyle(\pm2)^2\equiv4\pmod{47}, (\pm10)^2\equiv6\pmod{47}$
So, $\displaystyle(\pm2\cdot10)^2\equiv4\cdot6=24\implies x\equiv\pm20\pmod{47}\ \ \ \ (1)$
Similarly,  $\displaystyle x^2\equiv1293\pmod{47\cdot71}\implies x^2\equiv1293\pmod{71}\equiv15$
$\displaystyle x^2\equiv15\pmod{71}\equiv15+3\cdot71=228$ 
Setting $x=2y\implies y^2\equiv57\equiv57+71=128=2^7$
Setting $y=8z\implies z^2\equiv2\pmod{71}\equiv2+2\cdot71=12^2\implies z\equiv\pm12$
$x=2y=2(8z)=16(\pm12)=\pm192\equiv\pm50\pmod{71}\  \ \ \ (2)$
Then apply CRT on $(1),(2)$ to find all the four solutions
A: Hint: By the Chinese Remainder Theorem,  $$x^2 \equiv 1293 \mod 3337\\ \iff\\ x^2 \equiv 1293 \mod 47\ \ \text{ and }x^2\ \ \equiv 1293 \mod 71$$
You can then solve these slightly easier equations and piece things back together with the Chinese Remainder Theorem again.
Warning: each of these equations (mod $47$ and $71$) has two solutions, so overall you will have $4$ solutions. (This is because $3337$ is not prime, and hence $\mathbb Z / (3337\mathbb Z)$ is not an integral domain.)

In general, with this kind of question, the easiest solution will often be to break the problem up into smaller, easily solvable pieces using the Chinese Remainder Theorem, and then piece things back together.
