Number of elements that exist so $b^3 \equiv a\pmod n$, when n is composed of p and q who are prime numbers

Question

Given $2$ prime numbers,$ p$ and $q$, that are both not even, and $3$ doesn't divide $p-1$ or $q-1$, and $n=pq$, how many elements in $Z^*_n$ exists that has $b$ such that $b^3\equiv a\pmod n$ .

I know that the answer is $\phi(n)$ - that is, $(p-1)*(q-1)$, but I can't find out how to prove it :(

Answer 1

Let $a \in \Bbb (Z/n \Bbb Z)^\times$. We show that there is $k$ such that we can choose $b=a^k$, so $a^{3k}\equiv a \mod n$.

By Fermat's Little Theorem, we have $a^{\varphi(n)}\equiv 1 \mod n$.

As $3 \nmid (p-1)(q-1) = \varphi(n)$, we know $\gcd(3,\varphi(n)) = 1$. So by the Euclidean Algorithm you can choose $k \in \Bbb N$ such that $3k \equiv 1 \mod \varphi(n)$.

Now prove that $k$ has the desired property, i. e. $(a^k) ^3 \equiv a \mod n$

Answer 2

$\rm x\mapsto x^3$ is onto, being $1$-$1\!:$ $\, \begin{eqnarray}\rm a^3 &=&\rm b^3\\\Rightarrow\rm (a/b)^3 &=& 1\end{eqnarray}\!$ so $\rm\,a/b\,$ has order $\,n\mid 3,\phi,\,$ so $\,n\mid (3,\phi) = 1\ \ $ QED