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?

-
+1 for showing some thought. A well-posed question. – Ross Millikan Aug 3 '11 at 0:11
The other direction is easy but enlightening. $(2^{a-1}\pm 1)^2=2^a\pm 2\cdot2^{a-1}+1\equiv 1 \pmod{2^a}$ and it shows the other factor of $2$ comes from the cross term in the square, which is why you don't get any more as $a$ increases. – Ross Millikan Aug 3 '11 at 1:10

2 Answers

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?

-
I just fixed a small typo in your answer (adding a period). – Akhil Mathew Aug 3 '11 at 0:15
Thanks Pete L. Clark. I'm not too familiar with this, but here's what I think I gathered. I want to count all elements of order $2$ in $Z_2\times Z_{2^{a-2}}$? This is the same as the number of elements $(1,b)$ where $b$ has order $2$ in $Z_{2^{a-1}}$? But isn't $b=x^{2^{a-3}}$, where $x$ is the generator of $Z_{2^{a-2}}$ the only such element? Shouldn't I be counting 3 elements of order 2? – Joe Swanson Aug 3 '11 at 0:22
@Joe: close. You want all the elements of order at most $2$ in the product (of course the only element of order $1$ is the identity). It turns out that an element $(x,y)$ in a direct product has order at most $2$ iff both $x$ and $y$ have order at most $2$. – Pete L. Clark Aug 3 '11 at 0:51
Oops, I was just looking at elements of order $2$, not at most $2$. The 4 elements would be $(1,\pm 1)$ and $(1, \pm x^{2^{a-3}})$, so there are exactly 4 elements of order at most 2 in $U(2^a)$. Thanks, I really like this view of the problem. – Joe Swanson Aug 3 '11 at 0:59
@Joe: Not quite. When we switched to the notation $\mathbf{Z}_2\times\mathbf{Z}_{2^{a-2}}$ the group operation became componentwise addition. So the four elements of order at most 2 are $(0,0)$, $(1,0)$, $(0,2^{a-3})$ and $(1,2^{a-3})$. The isomorphism maps these back to the multiplicative group. You are correct in that in a cyclic group of even order there is only a single element of order two. But here the group is a direct sum/product of two cyclic subgroups, and you have the option to vary both components. – Jyrki Lahtonen Aug 3 '11 at 7:00

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

-
Thanks Bill Dubuque, that's pretty straightforward. – Joe Swanson Aug 3 '11 at 0:41