How many members $a$ in $\Bbb{Z}^*$ have a number $b$, $b^3 = a \pmod n$?

35 Views Asked by At

Given two prime numbers $p$ and $q$ such that $3$ does not divide $p-1$ nor $q-1$, and let $pq = n$.

How many numbers in $\mathbb{Z}_n^{*}$ (multiplicative group) are equal to some $b^3$ where $b$ is a number ?

How does the fact that $3$ doesn't divide $(p-1)$ and $(q-1)$ help me find the answer ? All I know is that the size of $\mathbb{Z}_n^{*}$ does not divide by $3$ (because its size is $(p-q)(q-1)$) but how does it help me ?

1

There are 1 best solutions below

0
On

Hint: If $3$ does not divide $p-1$, then $x \mapsto x^3$ is a bijection in $\mathbb Z_p$.