Exercise 3.3.11 (Solutions of $x^2 \equiv a \pmod {2^\alpha}$)

Proof. If $x^2\equiv a(\mathit{mod}{2}^{\alpha })$, where $\alpha \ge 3$, then $x^2\equiv a(\mathit{mod}8)$. Since $a$ is odd, $x$ is odd, so $x=2k+1$ for some integer $k$. Therefore $a\equiv x^2=8\frac{k(k+1)}{2}+1\equiv 1(\mathit{mod}8)$, so $a\equiv 1(\mathit{mod}8)$.

• If $a\not\equiv 1(\mathit{mod}8)$, we have proved that the congruence $x^2\equiv a(\mathit{mod}{2}^{\alpha })$ has no solution.

• Suppose now that $a\equiv 1(\mathit{mod}8)$. By Theorem 2.43, since $a$ is odd, there exists $i,j$ such that $a\equiv {(-1)}^i{5}^j(\mathit{mod}{2}^{\alpha })$, where $0\le i<2,0\le j<2^{\alpha -2}$. Reducing modulo $4$, this implies ${(-1)}^i\equiv a\equiv 1(\mathit{mod}4)$, therefore $i$ is even, and $a\equiv 5^j(\mathit{mod}{2}^{\alpha })$. Since $5^{2l}\equiv 25^l\equiv 1(\mathit{mod}8)$, and $5^{2l+1}\equiv 5(\mathit{mod}8)$, we obtain that $j$ is even, so that $j=2k$ for some integer $k$ $(0\le k<2^{\alpha -3})$ and

  $$a\equiv 5^{2k}(\mathit{mod}{2}^{\alpha }).$$

  We prove anew Corollary 2.44 in this particular case, to show that the congruence $x^2\equiv a(\mathit{mod}{2}^{\alpha })(\alpha \ge 3)$ has exactly $4$ solutions when $a\equiv 1(\mathit{mod}8)$. Since $a$ is odd, $x$ is odd, thus by Theorem 2.43, there are integers $u,t$ such that

  $$x={(-1)}^u{5}^t,0\le u<2,0\le t<2^{\alpha -2}.$$

  Then, the part “unicity” of Theorem 2.43 shows that

  $$\begin{array}{llll}\hfill x^2\equiv a(\mathit{mod}{2}^{\alpha })& ⟺{(-1)}^{2u}{5}^{2t}\equiv 5^{2k}& \hfill & \\ \hfill & ⟺\{\begin{array}{c}2u\equiv 0(\mathit{mod}2),\hfill \\ 2t\equiv 2k(\mathit{mod}{2}^{\alpha -2}).\hfill \end{array}& \hfill & \end{array}$$

  The first congruence is always true, so its solutions are $u=0,u=1$. The second is equivalent to $t\equiv k(\mathit{mod}{2}^{\alpha -3})$, where $0\le t<2^{\alpha -2}$ (and $0\le k<2^{\alpha -3}$). Therefore $k=0$ or $k=1$, and

  $$\{\begin{array}{cc}x\equiv \pm 5^k\hfill & (\mathit{mod}{2}^{\alpha }),\hfill \\ x\equiv \pm 5^k\cdot 5^{2^{\alpha -3}}\hfill & (\mathit{mod}{2}^{\alpha }).\hfill \end{array}$$

  Conversely, $\pm 5^k$ and $\pm 5^k\cdot 5^{2^{\alpha -3}}$ are solutions of the congruence, because ${(\pm 5^k)}^2=5^{2k}\equiv a(\mathit{mod}{2}^{\alpha })$, and ${(\pm 5^k\cdot 5^{2^{\alpha -3}})}^2=5^{2k}\cdot 5^{2^{\alpha -2}}\equiv a$ (recall that $5$ has order $2^{\alpha -2}$ modulo $2^{\alpha }$ by Theorem 2.43).

  Moreover, these $4$ solutions are distinct modulo $2^{\alpha }$. If ${(-1)}^u{5}^t\equiv {(-1)}^v{5}^s$ then ${(-1)}^u={(-1)}^v$, and $5^t\equiv 5^s{(\mathit{mod}2)}^{\alpha }$. Therefore $5^k\not\equiv -5^{k+2^{\alpha -3}},5^k\not\equiv -5^k$, and $-5^k\not\equiv 5^{k+2^{\alpha -3}}$. If $5^k\equiv 5^k\cdot 5^{2^{\alpha -3}}$, then $1\equiv 5^{2^{\alpha -3}}(\mathit{mod}{2}^{\alpha })$. This is impossible, since the order of $5$ is $2^{\alpha -2}$.

We have proved that the congruence $x^2\equiv a(\mathit{mod}{2}^{\alpha })$, where $a$ is odd, has $4$ solutions or no solution, according as $a\equiv 1(\mathit{mod}8)$ or not.

Suppose now that $x_0$ is one of these four solutions. Then ${(\pm x_0)}^2=x_0^2\equiv a(\mathit{mod}{2}^{\alpha })$ and

Since $2\alpha -2\ge \alpha$ (here $\alpha \ge 3$), and $2\cdot 2^{\alpha -1}=2^{\alpha }$, we obtain

Therefore $\pm x_0,\pm x_0+2^{\alpha -1}$ are solutions of the congruence $x^2\equiv a(\mathit{mod}{2}^{\alpha })$.

Moreover these solutions are distinct modulo $2^{\alpha }$. Indeed, the solution $x_0$ is odd, thus $x_0\not\equiv -x_0(\mathit{mod}{2}^{\alpha })$, otherwise $4\mid 2x_0$ and $2\mid x_0$. Similarly $x_0+2^{\alpha -1}\not\equiv -x_0+2^{\alpha -1}(\mathit{mod}{2}^{\alpha })$. Since $2^{\alpha }\nmid 2^{\alpha -1}$, $x_0\not\equiv x_0+2^{\alpha -1}(\mathit{mod}{2}^{\alpha })$. If $x_0\equiv -x_0+2^{\alpha -1}(\mathit{mod}{2}^{\alpha })$, then $2^{\alpha -1}\mid 2x_0$, and so $2^{\alpha -2}\mid x_0$. Since $\alpha \ge 3$, this implies that $x_0$ is even, which is false. This shows that $x_0\not\equiv -x_0+2^{\alpha -1}(\mathit{mod}{2}^{\alpha })$, and similarly $-x_0\not\equiv x_0+2^{\alpha -1}(\mathit{mod}{2}^{\alpha })$.

Therefore the four solutions of the congruence $x^2\equiv a(\mathit{mod}{2}^{\alpha })$ are $x_0,-x_0,x_0+2^{\alpha -1},-x_0+2^{\alpha -1}$. Let $\bar{u}$ denote the class of the integer $u$ in $\mathbb{Z}∕2^{\alpha }\mathbb{Z}$. Then

is the set of solutions of the equation $x^2=\bar{a}$ in $\mathbb{Z}∕2^{\alpha }\mathbb{Z}$, if $a\equiv 1(\mathit{mod}8)$ and $\alpha \ge 3$. □