Exercise 3.1.23* ( The congruence $x^2 \equiv a \pmod {p^\alpha}$ has $1 + \genfrac{(}{)}{}{}{a}{p}$ solutions)

Proof. Let $N_{\alpha }$ denote the number of solutions of $x^2\equiv a(\mathit{mod}{p}^{\alpha })$. We show first the proposition for $\alpha =1$.

• If $a$ is a quadratic nonresidue, then $x^2\equiv a(\mathit{mod}p)$ has no solution, so $N_1=0$, and $\left(\frac{a}{p}\right)=-1$, therefore $N_1=1+\left(\frac{a}{p}\right)$.
• If $a$ is a quadratic residue, then $N_1=2$, and $\left(\frac{a}{p}\right)=1$, therefore $N_1=1+\left(\frac{a}{p}\right)$.

In both cases

If $\alpha >1$, we apply the Hensel’s lemma (Theorem 2.23) to $f(x)=x^2-a$. Since $p$ is an odd prime, and $p\nmid a$, $f^{\prime }(a)=2a\not\equiv 0(\mathit{mod}p)$. Therefore, if $a_1,a_2$ are the two distinct solutions of $f(x)\equiv 0(\mathit{mod}p)$, there is a unique root $b_1$ of $f(x)$ modulo $p^{\alpha }$ that lies above $a_1$, and a unique root $b_2$ above $a_1$. So, if $a\wedge p=1$,

□