1
$\begingroup$

I'm trying to solve for 188 and 131, how do we get 188 and 131 using CRT?

I can calculate these, its just I do not get how to get 188 and 131.

√23 (mod 209)

√a (mod p) = ±a(p+1)/4, if p ≡ 3 (mod 4)

√4 (mod 11) = ±23^3(mod 11) = ±1

√4 (mod 11) = ±23^3(mod 11) = ±17

Using the CRT we can therefore calculate √ 23 (mod 209) as ±188, ±131

$\endgroup$
  • $\begingroup$ You combine the solutions mod $11$ and $19$ using CRT exactly as described in the duplicate. If that is not clear then ping me here and I will elaborate. $\endgroup$ – Bill Dubuque Jan 15 at 21:46
  • $\begingroup$ What are you trying to calculate, exactly? $\endgroup$ – Bernard Jan 15 at 21:48
  • $\begingroup$ See also here and here for more worked examples. $\endgroup$ – Bill Dubuque Jan 15 at 21:49
  • $\begingroup$ We seek solutions to $\,x\equiv a\equiv \pm1\pmod{\!11},\ x\equiv b\equiv \pm2\pmod{\!19}.\,$ Applying CRT wwe find a solution for $\,a,b = -1,2\,$ is $\,x\equiv 21\pmod{\!209}$ and its negative (corresponding to $\,a,b = 1,-2)$ $\endgroup$ – Bill Dubuque Jan 15 at 22:10
  • $\begingroup$ Similarly $\,a,b = 1,2\,$ yields $\,x\equiv 78\pmod{\!209}\,$ and its negative (for $\,a,b = -1,-2)\ $ $\endgroup$ – Bill Dubuque Jan 15 at 22:12

Browse other questions tagged or ask your own question.