3
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ That is exactly what I was looking for. Thank you! $\endgroup$ – Nescio May 3 '16 at 7:54
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.