Prove that $x^2\equiv a\pmod {2^m}$ has exactly 4 solutions if $a\equiv 1\pmod8$.

elementary-number-theorynumber theoryquadratic-residues

An excercise 11.6.17 of "Number Theory: A Lively Introduction With Proofs Applications and Stories" involves prooving the following theorem:

Let $a,m\in \Bbb Z, m \geq 3$. The equation $x^2\equiv a\pmod {2^m}$ has exactly 4 solutions if $a\equiv 1\pmod8$ and no solutions if $a\not\equiv 1\pmod8$.

There is hint for this problem with the outline of the proof I used to follow:

  1. Show that if $x\in \Bbb Z$ – odd, then $x^2\equiv 1\pmod8$. This one is easy to show as $8|x^2 -1 =(x – 1)(x + 1)$ for odd $x$.
  2. Using 1. show that $x^2\equiv a\pmod{2^m}$ has no solutions if $a\not\equiv1\pmod8$. That's also clear for me as if $x^2\equiv 1\pmod8$ then so does $a\equiv 1\pmod8$.
  3. Now use induction on $m$ to show that $x^2\equiv a\pmod{2^m}$ has exactly 4 solutions if $a\equiv 1\pmod8$. I'm starting from $m=3$ and showing directly that the entire solution set is $\{1, 3, 5, 7\}$.
  4. Then by induction hypothesis assume that $x^2\equiv a\pmod{2^m}$ has exactly 4 solutions. Considering $x_1$ as solution it's easy to show that $x_1 + 2^{m-1}$ is also a solution (no problem with that), so the entire set of solutions is $\{x_1, x_1 + 2^{m-1}, x_2, x_1 + 2^{m-1}\}$.
  5. Show that one of $x_1$ or $x_1 + 2^{m-1}$ solves $x^2\equiv a\pmod{2^{m+1}}$ (and so for $x_2$ or $x_2 + 2^{m-1}$).

Here is the step I'm stuck on. While I can see it clearly on numerical examples, I have no idea how to show it in general. I've tried substuting $x_1$ and $x_1 + 2^{m-1}$ in $x^2\equiv a\pmod{2^{m+1}}$ but it doesn't help much. But if I assume it's true, then I can finish the proof as follows:

  1. Since we have two solutions for $x^2\equiv a\pmod{2^{m+1}}$ from 5. we can get the other two by adding $2^m$ as in 4.
  2. Then since every solution of $x^2\equiv a\pmod{2^{m+1}}$ also solves $x^2\equiv a\pmod{2^{m}}$, and the last has exactly 4 solutions by induction hypothesis, it means that $x^2\equiv a\pmod{2^{m+1}}$ itself has exactly 4 solution. Thus, induction hypothesis is true and we are done.

So I'm asking for help with step 5. Thank you in advance for any thoughts.

BTW. this problem is from section that regards Jacobi Symbol. But actually I'm not sure how Jacobi Symbol could be applied here since we working with the even modulus.

Best Answer

Since $x_1$ is odd and $m \ge 3$:

$$(x_1 + 2^{m-1})^2 = x_1^2+2^mx_1+2^{2m-2} \equiv x_1^2+2^mx_1 \equiv x_1^2+2^m \pmod {2^{m+1}}$$

We also have $x_1^2 \equiv (x_1 + 2^{m-1})^2 \equiv a \pmod {2^m}$. Hence $x_1^2 \equiv a$ or $a+2^m \pmod {2^{m+1}}$.

If $x_1^2 \equiv a \pmod {2^{m+1}}$ we are done.

If $x_1^2 \equiv a+2^m \pmod {2^{m+1}}$ then

$$(x_1 + 2^{m-1})^2 \equiv x_1^2+2^m \equiv a+2^m+2^m \equiv a \pmod {2^{m+1}}$$

Hence either $x_1$ or $x_1 + 2^m$ solves $x^2 \equiv a \pmod {2^{m+1}}$.

Related Question