For an odd prime $p$, and some integer $b,n$. I'm interested in finding the number of solutions to $$x^2 \equiv b \mod p^n$$
Researching this led me into Hensel's lemma but I want to verify I understood correctly.
By Hensel's lemma, a solution $x_i$ to $f(x)\equiv 0 \text{ mod } p^i$ lifts to a unique solution modulo $p^{i+1}$ if and only if $p\nmid f'(x_i)$.
In the given case, $f'(x_i)=2x_i$ . Thus if $x_1$ is a solution for $x^2\equiv b \text{ mod } p$, then $p\nmid f'(x_1)$ and a $x_1$ will lift to a single solution, which will keep lifting using the same idea as always $x_i\equiv x_1\text{ mod } p$ which means that always $p\nmid x_i$ and $p\nmid 2x_i$.
Does that mean that the original congruence will always have exactly two solutions if $b$ is a quadratic residue mod $p$ or am I doing something wrong?
Best Answer
Your use of Hensel's Lemma works fine, if $b$ is co-prime to $p$. Here is another approach:
Let me deduce the following result without using Hensel's Lemma, but only basic group theory and some element-counting.
Proof:
$(\mathbb Z/p^n\mathbb Z)^*$ is a cyclic group of even order $N = p^{n-1}(p-1)$, hence it contains exactly one element of order $2$. Thus the kernel of the square map
$$(\mathbb Z/p^n\mathbb Z)^* \to (\mathbb Z/p^n\mathbb Z)^*, x \mapsto x^2$$ consists of two elements. This yields that the equation $x^2=b \pmod {p^n}$ has either two or zero solutions and precisely one half of all choices for $b$ belongs to either case.
Certainly, if $x^2=b \pmod p$ is not solvable, then $x^2=b \pmod {p^n}$ is not solvable for any $n$. Thus we have found $\frac{N}{2}$ choices for $b$ that yield no solutions (The quadratic non-residues). By our arguments above, we deduce that the other $\frac{N}{2}$ choices for $b$ must yield two solutions. These are precisely the quadratic residues modulo $p$.
Let us attack the general case, where $b=up^m$ with $0 \leq m < n$ and $u$ co-prime to $p$: Then you can easily show that $x^2=b \pmod {p^n}$ is solvable iff $x^2=u \pmod {p^n}$ is solvalbe and $m$ is even.