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

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
    Is there another square root besides the $\pm$ of the solution above?2012-05-07
  • 0
    EDIT: Sorry for the double comment.2012-05-07
  • 0
    @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.2012-05-07
  • 0
    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.2012-05-07
  • 0
    @Ivan: Ah, okay. I don't know, I'm afraid.2012-05-07
  • 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.](http://en.wikipedia.org/wiki/Fermat_number)2012-05-07
  • 0
    @Jyrki : Is there a danger that $ux \equiv -x$, i.e. that there might be repeats among $x,-x,ux,-ux$?2012-05-07
  • 0
    The reason I am so curious is because @Justin's formula and the entire discussion here doesn't care that $n$ is a Fermat number, but only that $n$ is divisible by 4.2012-05-07
  • 0
    @Ivan, no! If, for example, $ux\equiv -x\pmod{n}$, then $n$ has to divide $(u+1)x$. But $\gcd(2,n)=1$, so also $\gcd(x,n)=1$. Therefore $n$ has to divide $u+1$, or $u\equiv-1$.2012-05-07
  • 0
    @Ivan, then I would like to invite you to take a look at a more tractable case of $n=2^{12}+1=4097.$ Here $2^4+1=17$ will be a factor of $n$, the other factor being $2^8-2^4+1=241$. Now you can find a number $u$ such that $u\equiv1\pmod{17}$ and $u\equiv -1\pmod{241}$.2012-05-07
  • 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