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

  • 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

2

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.