Solving $x^2 \equiv 140 \pmod{221}$

Question

I'm stuck with the last part of this question: solve $x^2 \equiv 140 \pmod{221}$.

We know that $140 = 7 \times2^2\times5$ and $221 = 13 \times 17$.

We split the original congruence in two, so we have:

$x^2 \equiv 140 \pmod{13}$

$x^2 \equiv 140 \pmod{17}$

Applying the properties of moduli we have:

$x^2 \equiv 10\pmod{13} \rightarrow x=\pm6$

$x^2 \equiv 4\pmod{17} \rightarrow x=\pm2$

After this point, it's not clear for me how I can arrive to the complete solution. Any advice?

Answer 1

Now you use the Chinese Remainder Theorem. For instance, let $x\in\mathbb Z$ be such that $x\equiv6\pmod{13}$ and that $x\equiv-2\pmod{17}$. Since $13$ and $17$ are coprime, there are integers $\alpha$ and $\beta$ such that $13\alpha+17\beta=1$. Using the generalized Euclid algorithm, you get that, for instance, $1=4\times13-3\times17$. Therefore,$$8=6-(-2)=32\times13-24\times17.$$So,$$6-32\times13=-2-24\times17(=-410).$$So, take this number: $-410$. Or, better still, take $32$ ($-410\equiv32\pmod{221}$).

Answer 2

Note that $$x^2 -140\equiv x^2 -140-221=x^2−19^2=(x-19)(x+19)\pmod{221}.$$ It follows that $$x\equiv \pm 19\equiv \pm 6 \pmod{13}\quad\text{and}\quad x\equiv \pm 19\equiv \pm 2 \pmod{17}.$$ Hence we have four solutions (actually we already have two of them, i.e. $19$ and $-19$) that can be obtained by using the Chinese Remainder Theorem: $$\begin{cases}x\equiv 6 \pmod{13}\\ x\equiv 2 \pmod{17} \end{cases}\quad \begin{cases}x\equiv 6 \pmod{13}\\ x\equiv -2 \pmod{17} \end{cases}\\ \begin{cases}x\equiv -6 \pmod{13}\\ x\equiv 2 \pmod{17} \end{cases}\quad \begin{cases}x\equiv -6 \pmod{13}\\ x\equiv -2 \pmod{17} \end{cases}$$ Can you take it from here?

P.S. By the first remark, $\pm 19$ are two solutions and all you need is to solve just ONE system: $$\begin{cases}x\equiv 6 \pmod{13}\\ x\equiv -2 \pmod{17} \end{cases}$$ if $m$ is the solution then the fourth one is $-m$.