Chinese Remainder Theoram

Question

How do I evaluate all the square roots of 4 mod 33 using Chinese Remainder Theoram. I know we can use mod 33 = 11 x 3. I'm not sure how to proceed to the next step

Answer 1

Have you tried brute force? The numbers are small enough.

$2$ is an obvious one. To get the others, just keep adding $33$ repeatedly to $4$ and check if it's a perfect square at each step. Upper limit (the point when you can stop) is after $32 \times 32 = 1024$.

$13$ is the next one.

Actually, because the others will be negatives mod 33, you can already tell that $-2$ and $-13$, a.k.a. $31$ and $20$, will be answers as well. I only have to check up to $17$ for this reason (because $17 \equiv -16$ mod $33$).

So the full list is: $2, 13, 20, 31$

Answer 2

The square roots of $4$ mod $p$ for $p$ a prime are clearly $\pm 2$.

You now have to use the Chinese Remainder Theorem and solve $$ x \equiv \pm 2 \bmod 3, \quad x \equiv \pm 2 \bmod 11 $$ You'll get four solutions mod $33$.