1
$\begingroup$

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
    You want Hensel's lemma: http://en.wikipedia.org/wiki/Hensel's_lemma2011-04-07
  • 0
    @Qiaochu Yuan: Is there any other easier method? Thank you.2011-04-07
  • 1
    You can imitate the proof of Hensel's lemma in this special case. Hensel's lemma is not a particularly difficult method.2011-04-07
  • 3
    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$.2011-04-07
  • 0
    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?2011-04-07
  • 0
    @Kate The problem is that you're picking a particular value for $x$ for which it does not work. The problem is just saying that the congruence is solvable, or that it has some solution, not that it works for all values of $x$.2011-04-07
  • 0
    ahh, right. so for all e there exists and x. thanks for helping clarify.2011-04-07
  • 0
    @Qiaochu Yuan: Hensel's Lemma require integer coefficient $k > 2$, so how can I use this lemma in this case because $x^2 \equiv a$ means $k = 1$? Please correct me if I was wrong. Thank you.2011-04-07
  • 0
    @Chan: you have not used the fact that the equation must be solvable for all $e$.2011-04-07
  • 0
    @Quiaochu Yuan: But the `iff` means two directions, right? By that I meant, eventually we have to show that "If $a \equiv 1 \pmod{8}$ then $x^2 \equiv a \pmod{2^e}$ is solvable for all $e$", don't we?2011-04-07
  • 1
    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.2011-04-07

1 Answers 1