# 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?

-
By "maximum" do you mean the maximum number of solutions $x^2 \equiv a \mod n$ in the integers, for an integer $a$? Your question could mean a lot of things. – Patrick Da Silva Dec 29 '11 at 0:46
@PatrickDaSilva Yes. – Andrew MacFie Dec 29 '11 at 0:47
For odd $n$, it can have as many as $2^r$ where $r$ is the number of distinct prime factors of $n$. – Arturo Magidin Dec 29 '11 at 0:48
@ArturoMagidin What about $n=9, 0 \equiv 0^2 \equiv 3^2 \equiv 6^2 \pmod{9}$? – Andrew MacFie Dec 29 '11 at 1:06
factor $n$ and use chinese remainder theorem. for $p$ an odd prime, there are two solutions and these can be lifted to solutions mod $p^r$ by hensel's lemma en.wikipedia.org/wiki/Hensel's_lemma. – yoyo Dec 29 '11 at 1:06

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.

-
I'm interested in a tight upper bound. – Andrew MacFie Dec 29 '11 at 19:10
For example, say $f(n)$ is the maximum number of square roots of any element in $\mathbb{Z}_n$. If $f(n)$ is upperbounded by something like $2^{\omega(n)}$, where $\omega$ is this, like Arturo said above, then, since $\omega(n) \sim \log \log n$, $f(n)$ is bounded by something like $\log n$. – Andrew MacFie Dec 29 '11 at 19:45
You also get a lot with $x^2\equiv 3^{2n} \pmod{3^{2n+1}}$. – André Nicolas Dec 29 '11 at 20:56