Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the maximum number of square roots an element of $\mathbb{Z}_n$ can have?

share|improve this question
    
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
4  
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
show 1 more comment

1 Answer

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.

share|improve this answer
    
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
1  
You also get a lot with $x^2\equiv 3^{2n} \pmod{3^{2n+1}}$. –  André Nicolas Dec 29 '11 at 20:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.