If N is odd, composite and not-integer-power, then each quadratic residue mod N has at least four square roots mod N

Question

The statement:

"If $N$ is odd, composite and not a power of an integer, then each quadratic residue mod $N$ has at least four square roots mod $N$".

This is written in the book Goldreich, "Computational Complexity: A Conceptual Perspective", page 195. I think that it is a false statement, take $N = 15$ as an example.

What am I missing?

The very problem is that the next algorithm takes this statement as true!

Answer 1

Suppose $n=pq$. Any quadratic residue mod $n$ is a residue mod $p$ and a residue mod $q$ so has square roots $\pm r_p$ and $\pm r_q$ modulo $p$ and $q$ respectively. The Chinese Remainder Theorem guarantees a square root for each of the four choices of sign.

This argument can easily be adapted to products of more primes and of prime power factors - just deal with each prime separately and use CRT to combine them.

This assumes, of course, that you are working with residues coprime to $N$.