How many solutions are there to $x^2\equiv 1\pmod{2^a}$ when $a\geq 3$?

Solution 1:

In my opinion, Hensel's Lemma is a bit of overkill here. Anyway, when I teach undergraduate number theory I emphasize the connections to undergraduate algebra. Here you are trying to find the elements of order $2$ in the finite abelian group $U(2^a) = (\mathbb{Z}/2^a \mathbb{Z})^{\times}$, so it would be very helpful to know how this group decomposes as a product of cyclic groups.

This group structure is usually computed around the same time one shows that $U(p^a)$ is cyclic for all odd $p$. The answer is that for all $a \geq 3$, $U(2^a) \cong Z_2 \times Z_{2^{a-2}}$, i.e., it is isomorphic to the product of a cyclic group of order $2$ and a cyclic group of order $2^{a-2}$. See e.g. Theorem 1 here for a proof.

Can you see how to use this result to prove your conjecture?

Solution 2:

Hint $ $ It's easy: $\, d\ |\ x\!-\!1,\,x\!+\!1\, \Rightarrow\, d\ |\ x\!+\!1\!-\!(x\!-\!1) = 2.\,$ Thus if $\, 2^{a}\ |\ (x\!-\!1)(x\!+\!1)\:$ there are only a few ways to distribute the factors of $\,2\,$ such that $\,\gcd(x\!-\!1,x\!+\!1)\,$ is at most $\,2.$