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,
Best Answer
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$.