Exercise 3.20

Proof. Consider the equation $x^2\equiv 1(\mathit{mod}{2}^b)$.

$\text{∙}$ If $b=1$, $x^2\equiv 1(\mathit{mod}2)⟺2\mid (x-1)(x+1)⟺x\equiv 1(mod2)$: we obtain one solution.

$\text{∙}$ If $b=2$, as $0^2\equiv 2^2\equiv 0(\mathit{mod}4)$, $x^2\equiv 1(\mathit{mod}4)⟺x\equiv \pm 1(mod4)$: we obtain two solutions.

$\text{∙}$ Suppose that $b\ge 3$. The equation has 4 solutions $1,-1,1+2^{b-1},-1+2^{b-1}$.

Indeed, ${(\pm 1)}^2\equiv 1(\mathit{mod}{2}^b)$, and

and similarly ${(-1+2^{b-1})}^2\equiv 1(\mathit{mod}{2}^b)$.

These solutions are incongruent modulo $2^b$ :

$1\not\equiv -1(\mathit{mod}{2}^b)$ and $1+2^{b-1}\not\equiv -1+2^{b-1}$ (if not, $2^b\mid 2$, so $b\le 1$).

If $1+2^{b-1}\equiv -1(\mathit{mod}{2}^b)$, then $2^b\mid 2+2^{b-1}=2(1+2^{b-2})$, thus $2\mid 2^{b-1}\mid (1+2^{b-2})$, this is impossible because $1+2^{b-2}$ is odd ( $b\ge 3$). Therefore $-1+2^{b-1}\not\equiv 1(\mathit{mod}{2}^b)$. Moreover $1+2^{b-1}\equiv 1(\mathit{mod}{2}^b)$ implies $2^b\mid 2^{b-1}$, so $2\mid 1$ : this is a contradiction, so $1+2^{b-1}\not\equiv 1(\mathit{mod}{2}^b)$, and similarly $-1+2^{b-1}\not\equiv -1(\mathit{mod}{2}^b)$. There exist at least 4 solutions.

We show that these are the only solutions :

Indeed, if $x^2\equiv 1(\mathit{mod}{2}^b)$, $2^b\mid (x-1)(x+1)$, where $d=(x-1)\wedge (x+1)=2$.

As in Ex.3.19, if $d=1$, then $2^b\mid x-1$ or $2^b\mid x+1$, a fortiori $x\equiv \pm 1(\mathit{mod}{2}^{b-1})$.

If $d=2$, then $x$ is odd, and $2^b\mid 4\frac{x-1}{2}\frac{x+1}{2}$, so $2^{b-2}\mid \frac{x-1}{2}\frac{x+1}{2}$, with $\frac{x-1}{2}\wedge \frac{x+1}{2}=1$, so $2^{b-2}\mid \frac{x-1}{2}$ or $2^{b-2}\mid \frac{x+1}{2}$, that is $2^{b-1}\mid x-1$ or $2^{b-1}\mid x+1$, thus $x\equiv \pm 1(\mathit{mod}{2}^{b-1})$.

(Alternatively, we can prove this implication by induction.)

Hence every solution of $x^2\equiv 1(\mathit{mod}{2}^b),b\ge 3$ is such that $x=\pm 1+k{2}^{b-1},k\in \mathbb{Z}$ : there exist only four such values in the interval $[0,2^b[$, namely $1,-1+2^{b-1},1+2^{b-1},-1+2^b$.

Conclusion: if $b\ge 3$, the roots of $x^2-1$ in $\mathbb{Z}∕2^b\mathbb{Z}$ are $\bar{1},-\bar{1},\bar{1}+{\bar{2}}^{b-1},-\bar{1}+{\bar{2}}^{b-1}$. □