0
$\begingroup$

I have an exam tomorrow and this was on one of the assignment sheets, I couldn't do it then and still can't!

Compute the square root of $2$ in $R=\mathbb{Z}/n\mathbb{Z}$ where $n=2^s+1$ and $s=2^k$

Any help would be greatly appreciated. The hint that was given was think in binary.

  • 0
    Have you tried doing it for $k=0,1,2,3$?2012-04-26
  • 0
    I forgot to include that k$\geq$ 2. I haven't tried doing that as already for k=2 n=17 and it gets very laborious very quickly.2012-04-26
  • 1
    Since $6^2=36\equiv 2\pmod{17}$, and it’s obvious that nothing smaller than $6$ works, it really isn’t very laborious for $k=2$.2012-04-26
  • 0
    But then the next n=257...2012-04-26

2 Answers 2