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

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

• You want Hensel's lemma: en.wikipedia.org/wiki/Hensel's_lemma – Qiaochu Yuan Apr 7 '11 at 1:14
• @Qiaochu Yuan: Is there any other easier method? Thank you. – Chan Apr 7 '11 at 1:21
• You can imitate the proof of Hensel's lemma in this special case. Hensel's lemma is not a particularly difficult method. – Qiaochu Yuan Apr 7 '11 at 1:25
• 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$. – André Nicolas Apr 7 '11 at 1:29
• 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. – Henry Apr 7 '11 at 6:06

The statement is obviously not correct when $a$ is even. So we assume that $a$ is odd.
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.