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

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?

• This is true for $b$ co-prime to $p$. You have to take care of cases like $x^2=p \pmod{p^2}$.
– MooS
May 3, 2016 at 6:04

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.

• That is exactly what I was looking for. Thank you! May 3, 2016 at 7:54

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}$.

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.
The text passage contains a mathematical question about the number of solutions to a specific congruence equation, and it also provides an answer to this question. The structure of the content is a discussion of the problem, an explanation using Hensel's lemma, and a proof of the result.
single_question_with_answer
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Number of solutions to $x^2\equiv b \mod p^n$

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?

• This is true for $b$ co-prime to $p$. You have to take care of cases like $x^2=p \pmod{p^2}$.
– MooS
May 3, 2016 at 6:04

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.

• That is exactly what I was looking for. Thank you! May 3, 2016 at 7:54

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}$.

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.
user
The text passage contains a mathematical question about the number of solutions to a specific congruence equation, and it also provides an answer to this question. The structure of the content is a discussion of the problem, an explanation using Hensel's lemma, and a proof of the result.

TYPE: SINGLE_QUESTION_WITH_ANSWER