Maximum number of square roots of $a \in \mathbb{Z}_n$ What is the maximum number of square roots an element of $\mathbb{Z}_n$ can have?
 A: Let $n$ have prime power factorization 
$$n=\prod_{i=1}^w p_i^{k_i}.$$
By the Chinese Remainder Theorem, the number of solutions of $x^2\equiv a\pmod{n}$ is equal to $s_1s_2\cdots s_w$, where $s_i$ is the number of solutions of the congruence $x^2\equiv a \pmod{p^{k_i}}$.  So all we need to do is to find the number of solutions of 
$$x^2\equiv a \pmod{p^k},$$
for $p$ prime.  
A complete answer is complicated. The main difficulty is in determining whether $x^2\equiv a\pmod{p}$ has solutions. For that, a useful tool is the Law of Quadratic Reciprocity.  We concentrate instead on the number of solutions of $x^2\equiv a\pmod{p_k}$, when there is a solution.
The case $a$ not divisible by $p$: If $p$ is an odd prime, and $p$ does not divide $a$, the answer is simple. If the congruence $x^2\equiv a \pmod{p^k}$ has a solution, it has exactly $2$ solutions. 
The answer is a bit more complicated if $p=2$.  Suppose that $a$ is odd. Then 
$x^2\equiv a \pmod 2$ has exactly $1$ solution. The congruence $x^2\equiv a\pmod{2^2}$ is only solvable when $a\equiv 1\pmod{4}$, and there are then $2$ solutions. Finally, if $k \ge 3$, the congruence $x^2\equiv a\pmod{2^k}$ is solvable only when $a\equiv 1\pmod{8}$, and then there are exactly $4$ solutions.  
Now we give a partial examination of the cases that are usually neglected, namely cases where $a$ is divisible by possibly high powers of $p$. The easiest family to deal with is the congruence $x^2\equiv 0 \pmod{p^k}$.  
Case $a=0$: Let $p$ be prime. Then the congruence $x^2\equiv 0\pmod{p^k}$ has exactly $p^m$ solutions, where $m=\lfloor \frac{k}{2}\rfloor$.  The solutions in the interval $[0,p^k-1]$ are given, respectively, by $p^m t$ and $p^{m+1}t$, where $0 \le t \le p^m-1$.
General case, $p$ divides $a$:  Next we look at $x^2\equiv a \pmod{p^k}$, where $p$ is a prime that divides $a$, but such that $a \not\equiv 0\pmod{p^k}$.  We deal only with odd $p$.  (The case $p=2$ would take a few more lines, and we omit it for now.)
Let $a=p^b a'$, where $a'$ is not divisible by $p$, and $1 \le b<k$. If $b$ is odd, the congruence $x^2\equiv a\pmod{p^k}$ has no solution. This is easy to verify, by noting from $x^2\equiv a \pmod{p^k}$, where $p\mid a$ and $k \ge 2$, we get $p^2\mid a$. 
So let $b$ be even, say $b=2t$.  If $x^2\equiv p^{2t}a'\pmod{p^k}$, we find that that $x^2\equiv p^{2t-2}a' \pmod{p^{k-2}}$ is solvable. Keep lowering the index of $p$ in this way. We arrive at the congruence $x^2\equiv a'\pmod{p^{k-2t}}$. This will not have a solution unless $a'$ is a quadratic residue of $p$.  If $a'$ is a quadratic residue of $p$, the congruence  $x^2\equiv a'\pmod{p^{k-2t}}$ has $2$ solutions. Each of these solutions yields $p^t$ solutions modulo $p^k$.
The conclusion is that if the congruence $x^2\equiv a\pmod{p^k}$ has a solution, then the congruence has $2p^t$ solutions.   
