Ytukyg

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

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.

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/mmathbf 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 $nge3$, 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, $nge3$, 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.

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 ($pneq2$). 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 ypm bar x$) is a divisor of $0$, or equivalently ($bar ypm 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^2equiv 0$ mod $p^{n-v(a)}$, or equivalently $wequivpm 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 $2phi(p^{n-v(a)})$.