I am stuck at a homework problem to find the square root of a quadratic residue $b$ in $Z_n$ ($n$ is not a prime). Currently, I have figured out that there exists a number $a \in Z_n$ such that $a^2 \equiv 1$. If I understand the theory correctly, that means the order of $QR_n$ is a multiple of $2$. Since $QR_n$ is a subgroup of $Z_n^*$, it means the order of $Z_n^*$ is also a multiple of $2$. I tried to leverage this knowledge to factor $n$ (so that I can apply Chinese remainder theorem and find the quadratic residue more efficiently). However, my computation shows that $n$ does not admit a small factor (I have checked numbers less than $10000$) at all. How can that be? If $2 \;|\; \phi(n)$, that implies at least one of $3, 4, 6$ should divide $n$, right? (I used the table here to save some manual computation.)
Am I going in a wrong direction? Can someone give me a hint in terms of how to find the square roots more efficiently given that we know a number $a \in Z_n$ such that $a^2 \equiv 1$?