Equations over $\mathbb{Z}_{p^n}$

Question

Let $p>2$ be a prime number, $n$ a natural number and $a$ an element of $\mathbb{Z}_{p^n}$. Is it possible to count the number of solutions of $x^2=a$ in $\mathbb{Z}_{p^n}$?

For example if $a=0$ then it is easy but for the general case I have no idea.

Also It is clear that if $x^2=a$ has a solution in $\mathbb{Z}_{p^n}$ then it should have a solution in the field $\mathbb{Z}_{p}$.

Answer 1

Partial answer:

If $p$ does not divide $a$, then $x^2=a$ has zero or two solutions, because $x^2=1$ has two solutions since $\mathbb{Z}_{p^n}^{\times}$ is cyclic.

Answer 2

Your question has been asked a number of times on various math. sites, and complete answers exist (see e.g.(1)). I give here a sketch of an elementary proof, as well as closed formulas without detailed calculations. Denote by $\mathbf Z/m\mathbf Z$ (or $\mathbf Z/m$ for short (2)) the ring of integers mod $m$. We want to compute the number $s(n)$ of squares in $\mathbf Z/n$. By the CRT, we are brought back to compute $s(p^n)$, where $p$ is a prime. Denote by $s^*(p^n)$ the number of squares in the group $(\mathbf Z/m)^*$ of units (=invertible elements) of $\mathbf Z/m$ .

1) Let us first compute $s^*(p^n)$ for $p$ odd. It is classically known that in this case $(\mathbf Z/p^n)^*$ is a cyclic group of order $\phi(p^n)=p^{n-1}(p-1)$, hence $s^*(p^n)=\phi(p^n)/2$. The case $p=2$ is (as usual) technically more complicated, but the structure of $(\mathbf Z/2^n)^*$ is known, hence also $s^*(2^n)$ (no use to write it down).

2) The non units of $\mathbf Z/p^n$ are the classes mod $p^n$ of the multiples of $p$ in $\mathbf Z$. For $n\ge3$, it is straightforward to show that $a$ mod $p^{n-2}$ is a square iff $ap^2$ mod $p^n$ is a square, and we can derive the recursion formula $s(p^n)=s^*(p^n)+s(p^{n-2})$. For $n=1,2$, direct computation shows that $s(p)=(p+1)/2$ (obviously) and $s(p^2)=s^*(p^2)+1=(p^2-p+2)/2$ (without difficulty). Applying the recursion formula for $p$ odd, $n\ge3$, we get $s(p^n)=(p^{n+1}+p+2)/2$ (resp. $(p^{n+1}+2p+1)/2(p+1)$) if $n$ is even (resp. odd), see (1). Analogous formulas exist for $p=2$.

(1) W. D. Stangl, "Counting squares in $\mathbf Z_n$", Math. Magazine, 69,4 (1994), 285-289.

(2) As a number theorist, I'm 200% against the notation $\mathbf Z_n$, at least because $\mathbf Z_p$ is reserved for the ring of $p$-adic integers and, from this view point (that of $p$-adic completion), $\mathbf Z_n$ makes no sense.

Answer 3

Oh! Sorry, I was careless. But the answer to your original question is elementary enough. For convenience, write $\bar x$ for the class of $x$ mod $p^n$. We keep in store the properties of $\mathbf Z/p^n$ recalled above ($p\neq2$). Suppose that $\bar a \neq \bar0$ is a square, say $\bar a={\bar x}^2$, and look for all $\bar y$ s.t. ${\bar y}^2={\bar x}^2$. Obviously, $\bar a$ is a unit iff $\bar x$ is, so we distinguish 2 cases:

1) $\bar a$ is a unit: then ${\bar y}^2={\bar x}^2$ iff $({\bar y}{\bar x}^{-1})^2=\bar 1$, iff $\bar y=\pm \bar x$ (we are working in the cyclic group of units).

2) $\bar a$ is not a unit: by our previous characterization of the non-units, this is equivalent to $x$ being a multiple of $p$. The equation ${\bar y}^2={\bar x}^2$ can be written as $(\bar y+\bar x)(\bar y-\bar x)=\bar 0$. This implies that ($\bar y\pm \bar x$) is a divisor of $0$, or equivalently ($\bar y\pm \bar x$) is a non-unit, or $y \equiv \pm x$ mod $p$. Denote by $v(.)$ the $p$-adic valuation and write $x=up^{v(x)}, y=wp^{v(y)}$ in $\mathbf Z$, with $p \nmid uw$. Note that $\bar a \neq \bar0$ means that $v(a)<n$, hence $\bar a={\bar y}^2={\bar x}^2$ implies that $2v(x)=2v(y)=v(a)\le n$. Thus $y^2-x^2=p^{v(a)}(w^2-u^2)$ and the equation $y^2-x^2=kp^n$ means that $w^2-u^2\equiv 0$ mod $p^{n-v(a)}$, or equivalently $w\equiv\pm u$ mod $p^{n-v(a)}$ since $\bar w, \bar u$ are units mod $p$.

Summarizing, the number of square roots of a given $\bar a$ is $0$, or $2$, or $2\phi(p^{n-v(a)})$.