Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 10 down vote favorite
1

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?

share|improve this question
2  
+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

up vote 6 down vote accepted

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?

share|improve this answer
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
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. – Jyrki Lahtonen Aug 3 '11 at 7:00
up vote 7 down vote

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

share|improve this answer
Thanks Bill Dubuque, that's pretty straightforward. – Joe Swanson Aug 3 '11 at 0:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.