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$
2
$\begingroup$
elementary-number-theory
modular-arithmetic
-
0By "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. – 2011-12-29
-
0@PatrickDaSilva Yes. – 2011-12-29
-
4For odd $n$, it can have as many as $2^r$ where $r$ is the number of distinct prime factors of $n$. – 2011-12-29
-
0@ArturoMagidin What about $n=9, 0 \equiv 0^2 \equiv 3^2 \equiv 6^2 \pmod{9}$? – 2011-12-29
-
0factor $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 http://en.wikipedia.org/wiki/Hensel's_lemma. – 2011-12-29
-
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