# 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
for all e? if I expand $x^2 \cong 8k+1(mod 2^e)$ to $x^2 = 2^em + 8k + 1$ and for all e means it should work when e=1 and x=6 which comes out to say 35 is a multiple of 2? or am I making an error here? –  Kate Apr 7 '11 at 2:04

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.

-