2
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Nosrati, Bill Dubuque elementary-number-theory Dec 3 '18 at 17:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alessar Dec 3 '18 at 10:08
  • 1
    $\begingroup$ I think that using the Euclid algorithm is the natural way to do it. $\endgroup$ – José Carlos Santos Dec 3 '18 at 10:09
  • $\begingroup$ Thanks for the answer $\endgroup$ – Alessar Dec 3 '18 at 10:14
  • 1
    $\begingroup$ @Alessar I've edited my answer. Thank you. $\endgroup$ – José Carlos Santos Dec 3 '18 at 10:54
  • 1
    $\begingroup$ From $6-2=17\times(-12)+13\times16$, you should have deduced that $$6-13\times16=2+17\times(-12)=-202\equiv9\pmod{221}.$$ $\endgroup$ – José Carlos Santos Dec 3 '18 at 11:57
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Alessar Dec 3 '18 at 10:12
  • 1
    $\begingroup$ @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. $\endgroup$ – Robert Z Dec 3 '18 at 10:16
  • $\begingroup$ 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 $\endgroup$ – Alessar Dec 3 '18 at 10:18
  • 1
    $\begingroup$ @Alessar I edited my answer with a P.S. have a nice day! $\endgroup$ – Robert Z Dec 3 '18 at 10:29
  • 1
    $\begingroup$ Dear downvoter, what's the problem with my answer? If there is something wrong please help me to improve it. $\endgroup$ – Robert Z Dec 3 '18 at 11:06

Not the answer you're looking for? Browse other questions tagged or ask your own question.