13
$\begingroup$

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?

2 Answers 2

8

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?

  • 1
    @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.2011-08-03
7

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.$

  • 0
    Thanks Bill Dubuque, that's pretty straightforward.2011-08-03