# Solutions for $x^2 \equiv 1 \pmod {2^k}$

What are the incongruent solutions for $x^2 \equiv 1 \pmod {2^k}$?

I tested it with a couple small values and came up with the answer and proof.

The answer is, if $k \ge 3, x \in \{1,2^{k-1}-1,2^{k-1}+1,2^k-1\}$.

Also note the lemma that if $2^{k+1}|n \Rightarrow 2^{k}|n$, which is trivial.

Then the proof by induction:

If $k = 3$, it is easy to check that the answer is correct.

Assume that the claim holds for $k \le n$.

Assume $k=n+1$. By the induction hypothesis, we see that $x^2 \equiv 1 \pmod {2^n}$ has four solutions: $\{1,2^{n-1}-1,2^{n-1}+1,2^n-1\}$. Because congruence is symmetric, we also see that $\{2^n+1,3*2^{n-1}-1,3*2^{n}+1,2^{n+1}-1\}$ are solutions.

Now apply the lemma and we see that the set of solutions for $x^2 \equiv 1 \pmod {2^{n+1}}$ is some kind of subset of the set of solutions for $x^2 \equiv 1 \pmod {2^n}$. This means that we only need to check the eight solutions generated above and select the correct ones.

We immediately see that the four solutions implied in the original statement are solutions. To test that the other four are not solutions, I give as an example the case $x=3*2^{n-1}-1$:

$(3*2^{n-1}-1)^2 = 1-3*2^n+9*2^{-2+2 n} = 1-2^n-0+2^{2*n-2}+2^n=1+2^{n-3} \neq 1 \pmod {2^{n+1}}.$

Others in the same way.

By the induction principle, the proof is finished.

Is the proof OK? And how do you prove it without knowing the set of solutions beforehand?

-

I think the way to get the answer without knowing it beforehand is this: $x^2\equiv1\pmod{2^k}$ says $2^k$ divides $(x+1)(x-1)$. Clearly $x$ must be odd, and the gcd of $x+1$ and $x-1$ is $2$, so we have either $x+1$ or $x-1$ divisible by $2^{k-1}$. This leads right away to the four solutions (for $k\ge3$).
For $k\geq 3$, $(\mathbb{Z}/2^k)^\times\cong\mathbb{Z}/2^{k-2}\times\mathbb{Z}/2$ (You can prove this with a binomial theorem argument, showing that $5=1+4$ has order $2^{k-2}$). Thus there are exactly four solutions, corresponding to the identity and the three elements of order $2$ in $\mathbb{Z}/2^{k-2}\times\mathbb{Z}/2$.
$\pm 1$ are obviously solutions. A quick check reveals that $2^{k-1}\pm1$ also work.