1. x^2 mod 2^b

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

2. Originally Posted by chiph588@

Show that the congruence $x^2 \equiv 1 \mod{2^b}$ has $4$ solutions when $b \geq 3.$
first see that $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 $x=2^rs + 1,$ where

$r \geq 1,$ and $s$ is an odd number. then: $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. $r > 1$: then $2^{r-1}s + 1$ and $s$ are both odd and thus (1) gives us: $r \geq b-1.$ thus: $x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.$

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

3. Originally Posted by NonCommAlg
first see that $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 $x=2^rs + 1,$ where

$r \geq 1,$ and $s$ is an odd number. then: $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. $r > 1$: then $2^{r-1}s + 1$ and $s$ are both odd and thus (1) gives us: $r \geq b-1.$ thus: $x =2^r s + 1 \equiv 2^{b-1} + 1 \ \text{or} \ 1 \mod 2^b.$

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

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

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