Exercise 2.6.10 (Solutions to $x^2 \equiv a \pmod{p^j}$)

Proof. By hypothesis, there is a solution $x_1$ to the congruence $f(x)=x^2-a\equiv 0(\mathit{mod}p)$. Moreover $a\not\equiv 0(\mathit{mod}p)$, thus $x_1\not\equiv 0(\mathit{mod}p)$.

Assume for induction that there is some integer $x_j\equiv x_1(\mathit{mod}p)$ such that $f(x_j)=x_j^2-a\equiv 0(\mathit{mod}{p}^j)$. Then $x_j=x_1+\mathit{\lambda p}$ for some integer $\lambda$.

Here $f^{\prime }(x)=2x$, so $f^{\prime }(x_j)=2x_j\not\equiv 0(\mathit{mod}p)$, because $p$ is odd, and $p\nmid x_0=x_j-\mathit{\lambda p}$, thus $p\nmid x_j$. The Hensel’s lemma shows that there exists an integer $t$ such that $f(x_j+t{p}^j)\equiv 0(\mathit{mod}{p}^{j+1})$. If we define $x_{j+1}=x_j+t{p}^j$, then $x_{j+1}\equiv x_j\equiv x_1(\mathit{mod}p)$, and $f(x_{j+1})\equiv 0(\mathit{mod}{p}^{j+1})$, so $x_{j+1}^2\equiv a(\mathit{mod}{p}^{j+1})$. The induction is done.

This induction proves that $x^2\equiv a(\mathit{mod}{p}^j)$ has a solution for all $j\ge 1$, if there is a solution for $j=1$. □