Prove that $x^2 \equiv a \pmod{2^e}$ is solvable $\forall e$ iff $a \equiv 1 \pmod{8}$.

Whenever I encounter congruence proof, I'm stuck right away. How can I link $a \equiv 1 \pmod{8}$ with the $a$ in the quadratic congruence equation? The only thing that I know from the top of my head is, to express $a = 8k + 1$, then plug it into the congruence equation to get $x^2 \equiv 8k + 1 \pmod{2^e}$. I still can't see anything from here. I feel like I don't know exactly what do I need to show. Can anyone lecture me on this? Quadratic residue is so confusing, I really can't see its practical purpose.

Thank you

  • 3
    $\begingroup$ You want Hensel's lemma: en.wikipedia.org/wiki/Hensel's_lemma $\endgroup$ – Qiaochu Yuan Apr 7 '11 at 1:14
  • $\begingroup$ @Qiaochu Yuan: Is there any other easier method? Thank you. $\endgroup$ – Chan Apr 7 '11 at 1:21
  • 1
    $\begingroup$ You can imitate the proof of Hensel's lemma in this special case. Hensel's lemma is not a particularly difficult method. $\endgroup$ – Qiaochu Yuan Apr 7 '11 at 1:25
  • 4
    $\begingroup$ The statement of the result is not quite correct. Presumably you want to assume that $a$ is odd. Note since that the congruence $x^2 \equiv 0 \pmod{2^e}$ is always solvable, as is $x^2 \equiv 4$. $\endgroup$ – André Nicolas Apr 7 '11 at 1:29
  • 1
    $\begingroup$ It might be worth looking at $(8k+1)^2$, $(8k+3)^2$, $(8k+5)^2$ and $(8k+7)^2$ $\mod 2, 4, 8, 16, 32, \text{ and } 64$ to see if you can spot a pattern. As user6312 says, there are counterexamples if $a$ is even. $\endgroup$ – Henry Apr 7 '11 at 6:06

The statement is obviously not correct when $a$ is even. So we assume that $a$ is odd.

Since "only if" part is trivial, we prove "if" part.

Suppose $a \equiv 1$ (mod $8$)

Since $a \equiv 1$ (mod $2$) and $a \equiv 1$ (mod $4$), $x^2 \equiv a$ (mod $2^e$) has a solution when $e \leq 3$.

Let $k \geq 3$. Suppose $x^2 \equiv a$ (mod $2^k$) has a solution $x_0$. It suffices to prove that $x^2 \equiv a$ (mod $2^{k+1}$) has a solution $y_0$.

Let $y_0 = x_0 + 2^{k-1}t$. We determine t such that $y_0^2 \equiv a$ (mod $2^{k+1}$). $y_0^2 \equiv x_0^2 + 2^k tx_0$ (mod $2^{k+1}$). Hence $y_0^2 - a \equiv x_0^2 -a + 2^k tx_0$ (mod $2^{k+1}$). It suffices to solve $x_0^2 - a + 2^k tx_0 \equiv 0$ (mod $2^{k+1}$). Since $x_0^2 \equiv a$ (mod $2^k$), $x_0^2 - a = 2^k c$ for some integer c. Hence $2^k c + 2^k tx_0 \equiv 0$ (mod $2^{k+1}$). Hence $c+ tx_0 \equiv 0$ (mod $2$). Since $x_0$ is odd, this has a solution $t$. Hence we are done.

| cite | improve this answer | |

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.