Group theory - How Many Elements in $\mathbb Z_n^*$

Question

Assume $p,q$ are two primes numbers which differ from each other, such that $3$ doesn't divide $(p-1)$ nor $(q-1)$. and let $n = pq$. For how many elements in $\mathbb Z_n^*$, exists a value $b$ such that $b^3 \equiv a \bmod n.$

Answer 1

Notice that $\mathbb Z_n^*\cong \mathbb Z_{p-1}\times \mathbb Z_{q-1}$. This is a consequence of CRT and the existence of primitive roots $\bmod p$.

So we have reduced this problem to finding the number of solutions to $b^3=a$ inside a product of two cyclic groups of order $p-1$ and $q-1$. ( We use additive notation for these groups now).

If we let $a=(a_1,a_2)$ and $b=(b_1,b_2)$ then we need $3a_1\equiv b_1\bmod p-1$, which has only one solution (the solution is $a_1\cong 3^{-1}b_1\bmod p-1)$. Notice that it is important that $3\nmid p-1$, as otherwise the inverse does not exist. Analogously $b_2$ is uniquely determined.

Conclusion: There is exactly one solution to $b^3\equiv a \bmod pq$, for any $a\in \mathbb Z_{pq}^*$.