Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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
1  
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
2  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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