# Prove that $x^{2} \equiv 1 \pmod{2^k}$ has exactly four incongruent solutions

Prove that $x^{2} \equiv 1 \pmod{2^k}$ has exactly four incongruent solutions.

My attempt:
We have, $x^2 - 1 = (x - 1) \times (x + 1)$, then $(x - 1)(x + 1) \equiv 0 \pmod{2^k}$ which implies,
$2^k|(x - 1)$ or $2^k|(x + 1) \implies x \equiv \pm 1 \pmod{2^k} (1)$
Furthermore, $2^{k-1} \equiv 0 \pmod{2^k} \Leftrightarrow 2^{k-1} + 1 \equiv 1 \pmod{2^k}$.
Multiply both sides by $-1$, we have another congruent namely $-(2^{k-1} + 1) \equiv -1 \pmod{2^k}$ Hence, $x \equiv \pm(1 + 2^{k-1}) \pmod{2^k} (2)$
From $(1)$ and $(2)$, we can conclude that $x^{2} \equiv 1 \pmod{2^k}$ have four incongruent solutions.

Am I in the right track?

Thanks,

-
No: $(x-1)(x+1)\equiv 0\bmod 2^k$ does not imply that either $x-1\equiv 0\bmod 2^k$ or $x+1\equiv 0\bmod 2^k$, because $\mathbb{Z}/2^k\mathbb{Z}$ is not an integral domain unless $k=1$. Furthermore, $2^{k-1}\not\equiv0\bmod 2^k$ (obviously). – Zev Chonoles Mar 5 '11 at 7:49
@Zev Chonoles: Many thanks, I saw my wrong assumptions. Let me try it again. – Chan Mar 5 '11 at 7:54
You have correctly written down the four incongruent solutions (note that you actually need $k \geq 3$ for them to truly be inconruent), and it is easy to check that they are solutions. On the other hand, as Zev Chonoles notes, they way that you arrived at them is dubious, and in particular, you haven't proved that these are the only four solutions. – Matt E Mar 5 '11 at 7:55
The statement is only true if you are assuming $k\geq 3$, though. – Arturo Magidin Mar 5 '11 at 20:25

Note that $(x - 1)(x + 1) \equiv 0 \mod{2^k}$ will imply that $x$ must be an odd integer. So we may assume that $x = 2m + 1$. Putting value of $x$ in the equation we have $4m(m+1) \equiv 0 \mod{2^k}$. This means that $2^{k-2}$ divides $m(m+1)$ if I assume $k>2$. Note that if $k \leq 2$ then there is no condition on $m$. So all residue classes of odd integer satisfy the above equation. So now assume that $k > 2$. if $m$ is even then $m$ is divisible by $2^{k-2}$ and $x = 2^{k -1}t +1$ $t \in \mathbb{Z}$. But if $m$ is odd, then $m+1$ is divisible by $2^{k - 2}$ and in this case $x= 2(m +1)-1 = 2^{k-1}t - 1$ for $t \in \mathbb{Z}$. In the first we shall have only two non congruent solution namely $1$,$2^{k -1} +1$ whereas in the second case the incongruent solutions are $-1$ and $2^{k-1} - 1$.

-

Existence is easy:

The solutions are $\{1,2^{k-1}-1,2^{k-1}+1,2^k-1\}$.

Squaring them gives $\{1, 2^{2k-2}-2^k+1, 2^{2k-2}+2^k+1, 2^{2k}-2^{k+1}+1\}$.

Reducing $\pmod {2^k}$ gives 1 in each case (given that $2k-2 > k+1$, which forces $k \ge 3$).

For uniqueness you could use the fact that the units group of $\mathbb{Z}/2^k \mathbb{Z}$ is $C_2 \times C_{2^{k-2}}$ on the other hand that also gives existence..

-
You have missed $-1$ in the solution set. They will give the solution even for $k=0,1$. The only problem is that they wont be distinct in these cases. Please remove the typos in your solution. – A.G Mar 5 '11 at 14:52
Anjan -1 = n-1 (mod n). What typos? – quanta Mar 5 '11 at 15:16
What is the square of $2^k-1$? Reducing (modk) gives 1 in each case (given that 2k−2>k+1, which forces k≥3). I think it should be Reducing (mod$2^k$). They also reduce to $1$ even if $k = 2$ – A.G Mar 5 '11 at 16:17
Anjan: Thanks I fixed it now. – quanta Mar 5 '11 at 16:28

For any positive integer $n$, let $\mathbb{Z}/n\mathbb{Z}$ be the usual ring of integers modulo $n$ and let $U(n) = (\mathbb{Z}/n \mathbb{Z})^{\times}$ be its unit group -- i.e., the "reduced residues" modulo $n$ under multiplication.

Your question can be viewed as asking about the structure of this unit group when $n = 2^k$ for $k \geq 3$. (Note that $U(2)$ is the trivial group and $U(4)$ has order $2$, so the structure of these groups is clear.)

In fact it is a standard result -- at the border of undergraduate number theory and undergraduate algebra -- to give an exact computation of $U(n)$ for all positive integers $n$. See for instance Theorem 1 (and the discussion immediately preceding it, which reduces the general problem to the prime power case) of these notes. Especially, for all $k \geq 3$,

$U(2^k) \cong Z_2 \times Z_{2^{k-2}}$,

where here $Z_a$ denotes a cyclic group of order $a$. In a product $H_1 \times H_2$ of finite (multiplicatively written) commutative groups, an element $h = (h_1,h_2)$ satisfies $h^2 = 1$ iff this holds separately for both coordinates $h_1^2 = h_2^2 = 1$. Here $H_1$ and $H_2$ are both cyclic groups of even order, so each has exactly two elements which square to $1$, and thus $U(2^k)$ has $2 \times 2 = 4$ such elements.

Of course one can be much more explicit about what these elements are. This takes place in the proof of the result as well as in the answers others have given to this question.

-