2

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.

u123435
  • 173
  • 1
  • 5
  • 3
    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. – Sarvesh Ravichandran Iyer Mar 14 '17 at 05:25
  • 6
    $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 астон вілла олоф мэллбэрг – Jyrki Lahtonen Mar 14 '17 at 05:28
  • 1
    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 – Sarvesh Ravichandran Iyer Mar 14 '17 at 05:39
  • 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)$ – u123435 Mar 14 '17 at 05:39
  • Correct. Both those congruences have two non-congruent solutions, so you get four combinations. – Jyrki Lahtonen Mar 14 '17 at 06:07
  • @JyrkiLahtonen I solved both to get $x = 3,4$ and $x=6,11$. Not sure how to proceed from here. – u123435 Mar 14 '17 at 06:27
  • So far so good. The next step would be to combine $x\equiv3\pmod7$ and $x\equiv 6\pmod {17}$ using CRT to find a solution modulo $7\cdot17$. I'm relatively confident that your textbook has examples. That WP article explains a few techniques. Then do the same for the other three pairs. – Jyrki Lahtonen Mar 14 '17 at 06:31

0 Answers0