# Number of solutions to $z^2 \equiv p^fb \pmod{p^e}$?

Let $p$ be an odd prime, and let $e \in \mathbb{Z}$ with $e>1$. Let $a$ be an integer of the form $a = p^fb$, where $0 \leq f< e$ and $p \nmid b$. Consider the integer solutions $z$ to the congruence $z^2 \equiv a \pmod{p^e}$. Show that a solution exists if and only $f$ is even and $b$ is quadratic residue modulo $p$ , in which case there are exactly $2p^f$ distinct solutions modulo $p^e$.

I have shown the existence of the solution but I have not been able to find the number of solutions of the congruence. I had tried somethings like $$p^{f/2} | z\\ (p^{f/2}c)^2 \equiv p^fb \pmod{p^e}\\c^2 \equiv b \pmod{p^{e-f}}$$ which has 2 solutions modulo $p^{e-f}$, but then I am stuck.

• I would find solutions to the identical mod $p$ congruence then attempt to lift solutions using Hensel's Lemma. – user47805 Mar 31 '13 at 9:16

Our general strategy here is to find solutions mod $p$ and "raise" them to a congruence of higher powers. We use the following fact: for raising solutions from congruence mod $p^i$ to $p^{i+1}$ there are three cases (I apologize for not providing proof, I'm pulling this out of my text). Where we define $x_i$ as a solution to $f(x)\equiv0\mod p^i$:
1. $f'(x_i)\not\equiv0\mod p$ implies that $x_i$ gives rise to a unique solution mod $p$.
2. $f'(x_i)\equiv0\not\equiv q_i$ (where $f(x_i)=p^iq_i$) implies that $x_i$ gives rise to no solutions mod $p^{i+1}$
3. $f'(x_i)\equiv0\equiv q_i$ (where $f(x_i)=p^iq_i$) implies that $x_i$ gives rise to $p$ solutions mod $p^{i+1}$
We begin by finding solutions $f(x)\equiv0 \mod p$. We have $z_1^2-p^fb\equiv0\mod p$ iff $z_1^2\equiv0\mod p$ iff $z_1\equiv 0\mod p$. Note that $f'(z_1)\equiv0\mod p$ and $f(z_1)=p(0-p^{f-1}b)$ and $0-p^{f-1}b\equiv0$. This allows us to say that $z_1$ raises $p$ solutions to the congruence mod $p^2$ of the form $z_2=0+np$ where $0\leq n \leq p-1$.
Now we need to generalize to the $j\leq f-1$ case which is trickier. If I have time later I'll try to come and finish this off.