How many solutions are there to $x^2\equiv 1\pmod{2^a}$ when $a\geq 3$? I know there is a result that says $x^2\equiv 1\pmod{p}$ has only $\pm 1$ as solutions for $p$ an odd prime. Experimenting with $p=2$ shows that this is no longer the case. I ran a few tests on WolframAlpha, and noticed a pattern that there seem to be $4$ solutions to $x^2\equiv 1\pmod{2^a}$ when $a\geq 3$, and they are $\pm 1$ and $2^{a-1}\pm 1$. This works fine for the first several cases, but I'm wondering how you would actually prove that these are the only 4 solutions?
 A: 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?
A: 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.$ 
A: More generally,  it's a standard result in number theory that if $a\equiv 1\pmod8$, then $$x^2\equiv a\pmod {2^\alpha}$$ has $2^2=4$ solutions for $\alpha \ge3$.
See Vinogradov, Elements of Number Theory,  Dover, p.$94$ for an even more general statement.
