2
$\begingroup$

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

  • 0
    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.2011-12-29
  • 0
    @PatrickDaSilva Yes.2011-12-29
  • 4
    For 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
  • 0
    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 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

1 Answers 1