Number of solutions to $x^2 = y^2$ in $\mathbb{Z}/n\mathbb{Z}$ Are there any well known bounds for the number of solutions to the equation
$$
x^2 \equiv y^2 \pmod{n}
$$
What about the case when we restrict to the case that $n$ is a prime power?

To give an idea of the type of result I was hoping for, I know of this similar result:

If $q$ is a prime power and $k \geqslant 3$, then $x^k \equiv y^k \pmod{q}$ has at most $8kq^{2(1-1/k)}$ solutions.

My question is whether there is a similar bound for the case $k = 2$, and more generally, when $k = 2$ and $q$ is not restricted to being a prime power.
 A: The essential ingredients have already been provided in the comments.
By the Chinese remainder theorem, the number of solutions is the product of the numbers of solutions for the maximal prime powers of $n$.
So consider $n=p^k$ and write $x^2-y^2=(x+y)(x-y)\equiv0\bmod n$. For $p\ne2$, there is a bijection between pairs $(x+y,x-y)$ and pairs $(x,y)$ (given by $x=\frac12((x+y)+(x-y))$ and $y=\frac12((x+y)-(x-y))$) so we can instead ask how many solutions $(r,s)$ there are to $rs\equiv0\bmod p^k$. 
I’ll use $p^j\mid\mid m$ to mean that $p^j$ is the highest power of $p$ that divides $m$. For $0\le j\le k$ there are $p^{k-j}$ residues $s$ with $p^j\mid s$, so for $0\le j\lt k$ there are $p^{k-j}-p^{k-j-1}$ residues $r$ with $p^j\mid\mid r$. As $p^k\mid rs$ exactly if $p^j\mid\mid r$ and $p^{k-j}\mid s$ for some $j$, there are
\begin{eqnarray}
n+\sum_{j=0}^{k-1}\left(p^{k-j}-p^{k-j-1}\right)p^j
&=&
n+\sum_{j=0}^{k-1}\left(p^k-p^{k-1}\right)
\\
&=&
n\left(1+k\left(1-\frac1p\right)\right)
\end{eqnarray}
pairs $rs$ with $n=p^k\mid rs$ (where the term $n$ is separate because the general term doesn’t apply for the case $j=k$), and thus this is also the number of pairs $(x,y)$ with $n=p^k\mid x^2-y^2$.
If $p=2$, then $r=x+y$ and $s=x-y$ must have the same parity, and if they do, each pair $(r,s)$ yields two different pairs $(x,y)$. Thus we must not count the $n$ pairs that we counted above where one of $r$ and $s$ is odd (and the other is $0$), and instead double the remaining count, for a count of $nk$.
