Solve quadratic congruence using the Chinese Remainder Theorem

Question

Solve $x^2 \equiv$ -1 (mod 205)
I have that as 205 = 5 x 41 this becomes:

$x^2$ $\equiv $ -1 (mod 5)
$x^2$ $\equiv $ -1 (mod 41)

then i'm not sure where to go. I can see 32 is a solution but I don't know how to get there properly! Thanks

Answer 1

As other users in comments have recommanded, because you have prime modulii and they are relatively small you can check the number form $1$ to $\frac{p-1}{2}$ and obtain solutions. But here's another one:

Try adding 5 or 41 respectively to the RHS until you get a square. So you need to find a square of the form $5k - 1$ and a square of $41n - 1$ for some $n,z \in \mathbb{Z}$. It's easy to obtain that $4$ is a square of the form $5k-1$ and $81$ is the square of the form $41n - 1$ so you have:

$$x^2 \equiv -1 \equiv 4 \pmod 5 \implies x \equiv \pm 2 \pmod 5$$ $$x^2 \equiv -1 \equiv 81 \pmod {41} \implies x \equiv \pm 9 \pmod {41}$$

Then you have 4 cases to check and you'll get $4$ solutions using Chinese Remainder Theorem.