Number of solutions to $x^2\equiv b \mod p^n$

Question

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?

Answer 1

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.

Let $p$ be an odd prime and $b$ co-prime to $p$, let $n$ be any integer. Then $x^2=b \pmod {p^n}$ has two solutions of $b$ is a quadratic residue and zero solutions in the other case.

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.

Answer 2

Suppose that $b$ is not divisible by the odd prime $p$, and $c^2\equiv b\pmod{p^n}$. Then $x^2\equiv b\pmod{p^n}$ has exactly two solutions. It has the obvious solution $x\equiv -c\pmod{p^n}$. We show there are no others.

For suppose that $x^2\equiv b\equiv c^2\pmod{p^n}$. Then $p^n$ divides $(x-c)(x+c)$. But since $p$ cannot divide $2c$, one of $x-c$ or $x+c$ is not divisible by $p$, and therefore the other is divisible by $p^n$.

It follows that $x\equiv c\pmod{p^n}$ or $x\equiv -c\pmod{p^n}$.

Answer 3

Since $p$ is odd and $p\nmid b$, the proof given by @André Nicolas can be easily formalized as follows : the cyclic group $W_n := (Z/p^nZ)^* $ admits exactly one cyclic subgroup of order $(p-1)$ and one of order $p^{n-1}$, and since these orders are co-prime, $W_n \cong F_p^* \times C_{p^{n-1}}$. Because $p$ is odd, $C_{p^{n-1}}=C_{p^{n-1}}^2$ and so $W_n / {W_n}^2 \cong F_p^* / {F_p^*}^2$. The desired result follows.