What is the maximum number of square roots an element of $\mathbb{Z}_n$ can have?
Maximum number of square roots of $a \in \mathbb{Z}_n$
-
0@Andrew: $0$ is$a$special case, because it cannot be reduced to the case of square roots of unity. Note that it also has a *unique* square root in $\mathbb{Z}_p$, rather than $0$ or $2$ as the other elements do. – 2011-12-29
1 Answers
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
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.
-
1You also get a lot with $x^2\equiv 3^{2n} \pmod{3^{2n+1}}$. – 2011-12-29