# Solving $x^2 \equiv 140 \pmod{221}$ [duplicate]

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?

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}$$).

• Thanks, very clear. So with the CRT I can combine the final solutions to obtain the desired answer. I must pass for the Euclide algorithm or there are other methods? Dec 3, 2018 at 10:08
• I think that using the Euclid algorithm is the natural way to do it. Dec 3, 2018 at 10:09
• Thanks for the answer Dec 3, 2018 at 10:14
• @Alessar I've edited my answer. Thank you. Dec 3, 2018 at 10:54
• From $6-2=17\times(-12)+13\times16$, you should have deduced that $$6-13\times16=2+17\times(-12)=-202\equiv9\pmod{221}.$$ Dec 3, 2018 at 11:57

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$$.

• I think I can, it's like solving a diophantine equation for each combination. Thanks for the answer, wish I could give two "correct answer" flag instead of one Dec 3, 2018 at 10:12
• @Alessar Actually here we have to solve just ONE system because, by the first remark, $\pm 19$ are two solutions and the fourth one is the opposite of the first one . As regards the flag, don't worry, I am fine with your choice. Dec 3, 2018 at 10:16
• thanks, you guys are so prepared and professional. Ok so $\pm 19$ are two solutions, and another one will be the solution of the other two system. The absolute values are two but specular, so 4 systems, 2 requested for the final solution Dec 3, 2018 at 10:18
• @Alessar I edited my answer with a P.S. have a nice day! Dec 3, 2018 at 10:29
• Dear downvoter, what's the problem with my answer? If there is something wrong please help me to improve it. Dec 3, 2018 at 11:06