# Using Hensel's Lemma to find the number of solutions.

I am trying to determine the number of solutions of the congruence

$x^2 ≡ 1 \mod 2^k$ when $k \ge 3$

The statement of Hensel's Lemma that I use is the following:

Attempt: $x \equiv 1,3,5,7 \mod 8$, and for all of these $\tau = 1$ so by (i) since we have 2 distinct solutions $\mod 4$ we have two distinct solutions $\mod 8$? This is where I get lost.

• You should begin applying the Theorem starting with $j=3$. How do you plan to meet the condition $j\ge 2\tau+1$ otherwise? – Jyrki Lahtonen Mar 24 '16 at 12:26
• @JyrkiLahtonen I understand that I must start with $j=3$, I just don't know how. Can you expand? – Mark Mar 24 '16 at 12:31
• So the theorem says that $b \equiv a \mod 4$ implies $f(b) \equiv f(a) \mod 8$ and $2 || f'(b)$. Also, there exists unique $t (\mod 2)$ such that $f(a + 4t) \equiv 0 \mod 8$. Then as $f(x)$ has 4 solutions mod 8...? @JyrkiLahtonen where do I go next? – Mark Mar 24 '16 at 12:38
• I guess you are expected to do something like the following $f(x)=x^2-1$ obviously, so $f'(x)=2x$ so $2\Vert f'(a)$ always. When applying the theorem at the level $j=3$ part (ii) tells you that by adding the correct multiple of 4 to a solution modulo 8 you get a solution modulo 16. This, applied to mod 8 solutions works as follows $1\mapsto 1$, $3\mapsto7$, $5\mapsto 9$, $7\mapsto 7$. We got $7$ twice, and appear to have lost a solution. But then we are to apply part (i) at the level $j=4$, and deduce that both $7$ and $15$ are solutions modulo $16$. Alternatively (may be also intended??) – Jyrki Lahtonen Mar 24 '16 at 13:09
• (cont'd) We were to add ALL even multiples of 4 to 1, and ALL odd multiples of 4 to 3 in the previous round when (j=3). – Jyrki Lahtonen Mar 24 '16 at 13:11

Let $k\ge 3$. We are trying to solve $x^2\equiv 1\pmod{2^k}$. For concreteness let $2^k=1024$. We want to solve the congruence $$(x-1)(x+1)\equiv 0\pmod{1024}.$$ So $x-1$ and $x+1$ will need to be consecutive even integers.
Of any two consecutive even integers, one is congruent to $2$ modulo $4$, and the other is congruent to $0$ modulo $4$. The one congruent to $2$ modulo $4$ has only one $2$ to contribute to the product $(x-1)(x+1)$. So the other one must supply the rest of the $2$'s.
Thus $(x-1)(x+1)$ is divisible by $1024$ if and only if one of $x-1$ and $x+1$ is divisible by $512$.
This gives the four solutions $x\equiv 1\pmod{1024}$, $x\equiv 513\pmod{1024}$, $x\equiv 1023\pmod{1024}$ and $x\equiv 511\pmod{1024}$.