Exercise 3.3.12 (Solvability of $x^2 \equiv a \pmod{p^\alpha}$)

Proof. Consider the congruence $x^2\equiv a(\mathit{mod}{p}^{\alpha })$ with $p$ a prime, $\alpha \ge 1$, $a=p^{\beta }b,b\wedge p=1$.

Suppose first that $\beta \ge \alpha$. Then $0$ is a solution of the congruence $x^2\equiv b{p}^{\beta }(\mathit{mod}{p}^{\alpha })$, so $x^2\equiv a(\mathit{mod}{p}^{\alpha })$ is solvable (some nonzero solutions, such as $x=p^{\lceil \alpha ∕2\rceil }$ also exist if $\alpha >1$).

Suppose now that $\beta <\alpha$.

If the congruence $x^2\equiv a(\mathit{mod}{p}^{\alpha })$ is solvable, then $x^2-b{p}^{\beta }=\lambda p^{\alpha }$ $(\lambda \in \mathbb{Z})$. If $\beta =0$, then $\beta$ is even, and if $\beta >0$, then $p\mid x^2$, thus $p\mid x$. Write $x=y{p}^{\gamma }$, where $\gamma \ge 1$ and $y\wedge p=1$. Then $p^{\beta }\mid y^2{p}^{2\gamma }$, where $p\wedge y=1$, thus $p^{\beta }\mid p^{2\gamma }$, so $\beta \le 2\gamma$, thus

If $2\gamma -\beta >0$, then $p\mid b$. Since $p\wedge b=1$, this is a contradiction, therefore $\beta =2\gamma$ is even. Moreover $y^2\equiv b(\mathit{mod}{p}^{\alpha -\beta })$, so that the congruence $x^2\equiv b(\mathit{mod}{p}^{\alpha -\beta })$ is solvable.

Conversely, suppose that $\beta$ is even, and suppose that the congruence $x^2\equiv b(\mathit{mod}{p}^{\alpha -\beta })$ is solvable. Write $\beta =2\gamma$, where $\gamma$ is an integer, which gives $a=p^{2\gamma }b,b\wedge p=1$. Let $y$ be a solution of this last congruence, so that $y^2\equiv b(\mathit{mod}{p}^{\alpha -2\gamma })$. Then

This shows that the congruence $x^2\equiv a(\mathit{mod}{p}^{\alpha })$ is solvable.

If $\beta \ge \alpha$ then the congruence is solvable, and that if $\beta <\alpha$ then the congruence is solvable if and only if $\beta$ is even and $x^2\equiv b(\mathit{mod}{p}^{\alpha -\beta })$ is solvable. □