Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
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$. –  Brian M. Scott Apr 26 '12 at 15:21
    
But then the next n=257... –  James Apr 26 '12 at 15:31
add comment

2 Answers 2

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$

share|improve this answer
    
Thank you very much for your help! –  James Apr 26 '12 at 17:11
add comment

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

share|improve this answer
    
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
1  
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
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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