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:enter image description here

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.

  • $\begingroup$ You should begin applying the Theorem starting with $j=3$. How do you plan to meet the condition $j\ge 2\tau+1$ otherwise? $\endgroup$ – Jyrki Lahtonen Mar 24 '16 at 12:26
  • $\begingroup$ @JyrkiLahtonen I understand that I must start with $j=3$, I just don't know how. Can you expand? $\endgroup$ – Mark Mar 24 '16 at 12:31
  • $\begingroup$ 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? $\endgroup$ – Mark Mar 24 '16 at 12:38
  • 1
    $\begingroup$ 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??) $\endgroup$ – Jyrki Lahtonen Mar 24 '16 at 13:09
  • 1
    $\begingroup$ (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). $\endgroup$ – Jyrki Lahtonen Mar 24 '16 at 13:11

The following is not really an answer to the question, since after the first sentence it does not mention Hensel's lemma.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.