2
$\begingroup$

How can I find all the square roots of $2$ in $\mathbb{Z}_{119}$.

I understand that I have to solve the equation $[x]^{2} = [2]$ in $\mathbb{Z}_{119}$, but I am not sure how to proceed.

$\endgroup$
  • 3
    $\begingroup$ I cannot recommend a method, but the first thing that really came into my mind was just adding $119+2 = 121= 11^2$, so $x=11,108$ are the answers, as we can check (I often do these questions in this manner, so that i know the answers before going through the procedure). For a method, I would recommend breaking $119 = 7*17$, and then combining the answers together. $\endgroup$ – астон вілла олоф мэллбэрг Mar 14 '17 at 5:25
  • 6
    $\begingroup$ $119=7\cdot17$, so solve it modulo $7$ and modulo $17$, and then ChineseRemainderTheoremCombine them to get all the four answers. Oops, I apparently spoilered the fact that it has solutions w.r.t. both factors. That was kinda clear as commented by астон вілла олоф мэллбэрг $\endgroup$ – Jyrki Lahtonen Mar 14 '17 at 5:28
  • 1
    $\begingroup$ My feeling is that $7$ and $17$ are relatively small numbers, so you should be able to solve the congruences for $7$ and $17$ by hand $\endgroup$ – астон вілла олоф мэллбэрг Mar 14 '17 at 5:39
  • $\begingroup$ I think I understand it now. Can you elaborate a little further. Would the two congruences be $x^2 \equiv 2 (mod 7)$ and $x^2 \equiv 2 (mod 17)$ $\endgroup$ – u123435 Mar 14 '17 at 5:39
  • $\begingroup$ Correct. Both those congruences have two non-congruent solutions, so you get four combinations. $\endgroup$ – Jyrki Lahtonen Mar 14 '17 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.