Exercise 2.2.9 (Solutions for $x^2 \equiv 1 \pmod{2^\alpha}$)

beginproof If $\alpha =1$, then $1$ is the unique solution of $x^2\equiv 1(mod2)$.

If $\alpha =2$, then $1$ and $3$ are the solutions of $x^2\equiv 1(mod4)$ (in the complete residue system $\{0,1,2,3\}$).

If $\alpha =3$, the solutions of $x^2\equiv 1(mod8)$ are $1,3,5,7$ (in the complete residue system $\{0,1,2,3,4,5,6,7,8\}$). So, for $\alpha =3$ the solutions are congruent to

Note first that for every $\alpha \ge 3$, $2^{\alpha -1}-1,2^{\alpha -1}+1,-1$ are four non congruent solutions, because ${(\pm 1)}^2=1$, and

because $2\alpha -2\ge \alpha$. Moreover, for $\alpha \ge 3$, $1<2^{\alpha -1}-1<2^{\alpha -1}+1<2^{\alpha }-1$, therefore the classes modulo $2^{\alpha }$ of these solutions are distinct.

Now consider the proposition $𝒫(\alpha )$ for $\alpha \ge 3$, defined by

We have already verified $𝒫(3)$. Now assume for induction $𝒫(\alpha )$, where $\alpha \ge 3$.

Suppose that $x^2\equiv 1(mod{2}^{\alpha +1})$. A fortiori, $x^2\equiv 1(mod{2}^{\alpha })$. The induction hypothesis shows that

Suppose for contradiction that $x_0=2^{\alpha -1}\pm 1$. Using $2\alpha -2\ge \alpha +1$,

so that

But $x^2\equiv 1(mod{2}^{\alpha +1})$, thus $\pm 2^{\alpha }\equiv 0(mod{2}^{\alpha +1})$, therefore $2\mid 1$. This is a contradiction, which proves that $x_0\ne 2^{\alpha -1}+1,x_0\ne 2^{\alpha -1}-1$, thus $x_0\in \{-1,1\}$. Therefore $x=\pm 1+k{2}^{\alpha }$.

• If $k$ is even, $k=2\lambda$ for some integer $\lambda$. So $x=\pm 1+\lambda 2^{\alpha +1}\equiv \pm 1(mod{2}^{\alpha +1})$.

• If $k$ is odd, $k=2\mu +1$ for some integer $\mu$. So $x=\pm 1+(2\lambda +1)2^{\alpha }\equiv 2^{\alpha }\pm 1(mod{2}^{\alpha +1})$.

We have proved that $x\equiv 1,2^{\alpha }-1,2^{\alpha }+1,-1(mod{2}^{\alpha +1})$, and the induction is done.

If $\alpha \ge 3$, the congruence $x^2\equiv 1(mod{2}^{\alpha })$ has precisely the four solutions $1,2^{\alpha -1}-1,2^{\alpha -1}+1,-1$.