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

Question

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,

Answer 1

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

Answer 2

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

Answer 3

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.