Can someone explain the definition of four square roots as it pertains to groups in Z*p?

Question

So I'm given the following as a problem:

When $p$ and $q$ are distinct odd primes and $N = pq$, the points in $Z^∗_N$ have either zero or four square roots. A quarter of the points have four square roots; the rest have no square root. The four square roots of $x ∈ Z^∗_N$ will look like $±a, ±b$. (Of course, −a means N − a since we’re working modulo N.) Suppose that I give you an efficient deterministic algorithm S that, on input x that has square roots, finds some square root. (If x does not have a square root, it returns ⊥.) Use S to make an efficient probabilistic algorithm F that factors N.

I am not asking for a solution to the problem, rather an understanding of what "four square roots" could possibly mean? How can a single element $x∈ Z^∗_N$ have "four square roots"?

Answer 1

"$x$ has four square roots" means there are four distinct elements $r$ in the group such that $r^2 = x$.

For example, in $\mathbf{Z}_{15}^\times$ the element $1$ has four square roots, which are $1$, $4$, $11$, and $14$ (note that $11 \equiv -4$ and $14 \equiv -1 \pmod{15}$).

Answer 2

I want to give a proof and solution here. Suppose $x^2 \equiv m\pmod{N}$ has a root $x=x_{0}$, then we can obtain another three roots as following:

Let $x_{0} \equiv x_{1}\pmod{p}$ and $x_{0} \equiv x_{2}\pmod{q}$ respectively.Thus,

• $x^2 \equiv m\pmod{p}$ has exactly two square roots, that's $x \equiv x_{1}\pmod{p}$ and $x \equiv p-x_{1}\pmod{p}$.
• similarly, $x^2 \equiv m\pmod{q}$ has exactly two square roots, that's $x \equiv x_{2}\pmod{q}$ and $x \equiv q-x_{2}\pmod{q}$.
  From Chinese Remainder Theorem, the congruence equation $x^2 \equiv m\pmod{N}$ has exactly four roots.They are the roots in the combination
  \begin{equation} \left\{ \begin{array}{cl} x \equiv x_{1}\pmod{p} & \\ & \\ x\equiv x_{2}\pmod{q} & \end {array}\right. \end{equation} \begin{equation} \left\{ \begin{array}{cl} x \equiv x_{1}\pmod{p} & \\ & \\ x\equiv q-x_{2}\pmod{q} & \end {array}\right. \end{equation} \begin{equation} \left\{ \begin{array}{cl} x \equiv p-x_{1}\pmod{p} & \\ & \\ x\equiv x_{2}\pmod{q} & \end {array}\right. \end{equation} \begin{equation} \left\{ \begin{array}{cl} x \equiv p-x_{1}\pmod{p} & \\ & \\ x\equiv q-x_{2}\pmod{q} & \end {array}\right. \end{equation} We denoted the first two equation's root by $a$, $b$, then ($N-a$) and ($N-b$) are respectively roots of the last two equations.
  From the above, the four square roots are $a$, $b$, ($N-a$) and ($N-b$).
  That is worth mentioning, when $p, q$ are Blum primes, i.e. $p\equiv q \equiv3 \pmod{4}$, $x \equiv\pm m^{\frac{p+1}{4}} \pmod{p}$ are exactly the roots of equation $x^2 \equiv m\pmod{p}$.