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

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.

-
Have you tried doing it for $k=0,1,2,3$? –  Phira Apr 26 '12 at 15:10
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. –  James Apr 26 '12 at 15:17
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$. –  Brian M. Scott Apr 26 '12 at 15:21
But then the next n=257... –  James Apr 26 '12 at 15:31

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$

-
Thank you very much for your help! –  James Apr 26 '12 at 17:11

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)\;.$$

-
Is there another square root besides the $\pm$ of the solution above? –  Ivan May 7 '12 at 17:20
EDIT: Sorry for the double comment. –  Ivan May 7 '12 at 17:27
@Ivan: I'm not what $\pm$ you mean; I wasn't trying to do anything more than show how one might discover Justin's solution, which at first looks rather magical. –  Brian M. Scott May 7 '12 at 17:37
Sorry, what I meant was that there are for sure 2 distinct solutions given by $x_1=2^{2^{k-2}}(2^{2^{k-1}}-1)$ and $x_2=2^{2^k}+1-x_1$. I was wondering if there are other roots besides these 2, I can't seem to find an argument against such a possibility. –  Ivan May 7 '12 at 17:51
To answer @Ivan's question. Let's select $k=5$, so $n=2^{32}+1=4294967297=641\cdot6700417$. The number $u=1366885067$ has the properties that $u\equiv 1\pmod{641}$ and $u\equiv-1\pmod{6700417}$. Thus the Chinese remainder theorem tells us that $u^2\equiv 1\pmod{n}$. This means that if $x$ is one square root of $2$ modulo $n$, then so are $\pm ux$. Something similar is always possible, if $n$ has several odd prime factors. There are no known cases with $k>4$, when this does not happen. –  Jyrki Lahtonen May 7 '12 at 20:31