2
$\begingroup$

Find the $4$ sq. roots of $100$ in $U_{209}$. Identify which square root of $100$ is square.

(Not the $4^{th}$ root, but the $4$ square roots). I honestly don't even know what this question is asking... All I can say is $\sqrt{100}$ is $10$. Don't know what that has to do with $U_{209}$.

$\endgroup$
1
  • $\begingroup$ For a less obvious solution, solve $x\equiv 10\pmod{11}$, $x\equiv -10\pmod{19}$ using the Chinese Remainder Theorem. $\endgroup$ – André Nicolas Jul 28 '14 at 3:31
5
$\begingroup$

I think $\mathrm U_{209}$ means $(\mathbf Z/209\mathbf Z)^\times$. It then asks for the four $1\leq x\leq 208$ such that $x^2\equiv 100 \pmod{209}$. It will be useful to note that $209=11\times 19$.

The square square root problem should then be: find $1\leq x \leq 208$ such that $x^4\equiv 100\pmod{209}$.

$\endgroup$
3
  • $\begingroup$ Thank you!! That helps so much! I understand it now. $\endgroup$ – B. L. Miller Jul 28 '14 at 3:29
  • $\begingroup$ @B.L.Miller: You could post your solution as an answer and accept it so we have such. This is encouraged. $\endgroup$ – Ross Millikan Jul 28 '14 at 3:48
  • $\begingroup$ Thank you, I just did! I'm new to this website, I don't quite understand how to use it yet. Thank you for the tip! $\endgroup$ – B. L. Miller Jul 28 '14 at 3:57
1
$\begingroup$

I used Euclid's algorithm to get $x= 10$, $x=67$, $x= 142$, and $x= 199$.

I did the same for the square square root and got $x=54$, $x= 98$, $x=111$, and $x=155$.

$\endgroup$
2
  • $\begingroup$ Note that you only need to use Euclid's algorithm to get the first two: note that 142=209-67 and 199=209-10. So these are equivalent modulo 209 to -67 and -10, and therefore square to 100. Same idea for the fourth roots. $\endgroup$ – Semiclassical Jul 28 '14 at 4:00
  • $\begingroup$ Hopefully you don't need Euclid's algorithm for the first one. $\endgroup$ – Dylan Stephano-Shachter Jul 28 '14 at 13:51

Your Answer

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

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