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
    But then the next n=257...2012-04-26

2 Answers 2

3

I'm not so good at thinking in binary, but I did manage to cobble together some formulas using base 10 arithmetic. (It is obvious that thinking in binary would help, though.)

$(2^{2^{k-2}}(2^{2^{k-1}} - 1))^2 = 2^{2^{k-1}}(2^{2^k} + 1) - 2^{2^k + 1} \equiv 2 \mod 2^{2^k} + 1$

0

In case it’s of interest to anyone, there is a reasonable elementary way to attack the problem semi-systematically and arrive at Justin’s answer.

$2^s\equiv -1\pmod n$, so $2^{s+1}\equiv -2\pmod n$, and we’d like to find $m$ so that $m^2\equiv -2^{s+1} \pmod n$. Suppose that $m=a-1$; then $m^2=a^2-2a+1$, and it’s tempting to try $a=2^s$. Unfortunately, then $m^2=2^{2s}-2^{s+1}+1$, and $2^{2s}+1$ is not a multiple of $2^s+1$, so we have to work harder to get a $-2^{s+1}$ term.

The middle term of a square is still a reasonable place to look, and that means considering something of the form $(2^a-2^b)^2$, where $a+b=s$. In other words, we hope for an $a$ such that $(2^a-2^{s-a})^2=2^{2a}+2^{2(s-a)}-2^{s+1}=r(2^s+1)-2^{s+1}$ for some integer $r$. Clearly we may assume that $a>s-a$ and set $b=s-a$ and $c=a-b$, so that we want $2^{2b+2c}+2^{2b}=r(2^{2b+c}+1)$, or $2^{2b}(2^{2c}+1)=r(2^{2b+c}+1)$. Clearly this requires that $r=2^{2b}$ and $2b+c=2c$. From the latter we get $c=2b$, so, since $2b+c=s$, we must have $c=s/2$ and $b=s/4$, i.e., $c=2^{2^{k-1}}$ and $b=2^{2^{k-2}}$. (At this point the reason for the restriction to $k\ge 2$ becomes clear.) The desired square root is then $2^a-2^b=2^{b+c}-2^b=2^{3\cdot 2^{k-2}}-2^{2^{k-2}}=2^{2^{k-2}}\left(2^{2^{k-1}}-1\right)\;.$

  • 0
    No, I agree with your argument, just saying that the formula still works: it gives 504 as a root, so there is no need to use Fermat's numbers.2012-05-07