1. ## x^2 mod 2^b

Show that the congruence $\displaystyle x^2 \equiv 1 \mod{2^b}$ has $\displaystyle 4$ solutions when $\displaystyle b \geq 3.$

2. Originally Posted by chiph588@

Show that the congruence $\displaystyle x^2 \equiv 1 \mod{2^b}$ has $\displaystyle 4$ solutions when $\displaystyle b \geq 3.$
first see that $\displaystyle x \equiv \pm 1, \ \text{or} \ 2^{b-1} \pm 1 \mod 2^b$ satisfy the equation. we want to show that there are no other solutions. obviously such solution has got to be odd. so let $\displaystyle x=2^rs + 1,$ where

$\displaystyle r \geq 1,$ and $\displaystyle s$ is an odd number. then: $\displaystyle x^2-1=2^{r+1}s(2^{r-1}s+1) \equiv 0 \mod 2^b,$ which we'll call it (1). now consider two cases:

case 1. $\displaystyle r > 1$: then $\displaystyle 2^{r-1}s + 1$ and $\displaystyle s$ are both odd and thus (1) gives us: $\displaystyle r \geq b-1.$ thus: $\displaystyle x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.$

case 2: $\displaystyle r=1$: in this case (1) gives us: $\displaystyle s(s+1) \equiv 0 \mod 2^{b-2}.$ but $\displaystyle s$ is odd. hence $\displaystyle s \equiv -1 \mod 2^{b-2}.$ therefore: $\displaystyle x=2s+1 \equiv -1 \mod 2^{b-1}.$ thus: $\displaystyle x \equiv 2^{b-1}-1 \ \text{or} \ -1 \mod 2^b. \ \Box$

3. Originally Posted by NonCommAlg
first see that $\displaystyle x \equiv \pm 1, \ \text{or} \ 2^{b-1} \pm 1 \mod 2^b$ satisfy the equation. we want to show that there are no other solutions. obviously such solution has got to be odd. so let $\displaystyle x=2^rs + 1,$ where

$\displaystyle r \geq 1,$ and $\displaystyle s$ is an odd number. then: $\displaystyle x^2-1=2^{r+1}s(2^{r-1}s+1) \equiv 0 \mod 2^b,$ which we'll call it (1). now consider two cases:

case 1. $\displaystyle r > 1$: then $\displaystyle 2^{r-1}s + 1$ and $\displaystyle s$ are both odd and thus (1) gives us: $\displaystyle r \geq b-1.$ thus: $\displaystyle x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.$

case 2: $\displaystyle r=1$: in this case (1) gives us: $\displaystyle s(s+1) \equiv 0 \mod 2^{b-2}.$ but $\displaystyle s$ is odd. hence $\displaystyle s \equiv -1 \mod 2^{b-2}.$ therefore: $\displaystyle x=2s+1 \equiv -1 \mod 2^{b-1}.$ thus: $\displaystyle x \equiv 2^{b-1}-1 \ \text{or} \ -1 \mod 2^b. \ \Box$
In case 2, why does $\displaystyle x=2s+1$?

4. Originally Posted by chiph588@
In case 2, why does $\displaystyle x=2s+1$?
Because $\displaystyle r=1$ and so $\displaystyle x=2^rs+1 = 2s+1$.
---

Here is another way to solve this problem. But it is overkill. It is a known result that $\displaystyle \mathbb{Z}_{2^b}^{\times}$ is isomorphic to $\displaystyle \mathbb{Z}_{2} \times \mathbb{Z}_{2^{b-2}}$ for $\displaystyle b\geq 3$.
Let $\displaystyle \phi: \mathbb{Z}_{2^b}^{\times} \to \mathbb{Z}_{2} \times \mathbb{Z}_{2^{b-2}}$ be an isomorphism.
An element $\displaystyle x\in \mathbb{Z}_{2^b}^{\times}$ satisfies $\displaystyle x^2 = 1$ if and only if $\displaystyle \phi(2x)=\phi(1)$ iff $\displaystyle 2\phi(x) = 0$.
Thus, there is a 1-to-1 corresponded between solutions to $\displaystyle x^2 = 1$ in $\displaystyle \mathbb{Z}_{2^b}^{\times}$ and solutions to $\displaystyle 2(x,y) = (0,0)$ in $\displaystyle \mathbb{Z}_{2} \times \mathbb{Z}_{2^{b-2}}$.
However, there are clearly 4 solutions to $\displaystyle 2(x,y)=(0,0)$.