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.
Please help.

  • $\begingroup$ I would find solutions to the identical mod $p$ congruence then attempt to lift solutions using Hensel's Lemma. $\endgroup$ – 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.

  • $\begingroup$ I cannot understand your answer since I donot know any advance number theory. I have studied only upto primitive roots, quadratic residues, reciprocity law etc(means the typical undergrad course on number theory) and this is the question from that. So, it must have some elementary solution. $\endgroup$ – Saurabh Mar 31 '13 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.