I'm having trouble with solving the following question:

Given two distinct prime numbers $p, q$ where $(p-1)$ and $(q-1)$ are not divisible by $3$, define $n=pq$.

For how many elements in $\mathbb Z^*_n$ $\exists b$ for which: $b^3\equiv a\ (mod\ n)$

Given the fact that $|\mathbb Z^*_n| = \phi(n)=(p-1)(q-1)$, I could conclude that the number of elements are dependent on $p$ and $q$.

But I'm not sure how to tie together that fact with that $(p-1)$ and $(q-1)$ are not divisible by 3.

I tried to use Fermat's Little Theorem, but since $n=pq$ is not a prime number, it didn't seem to help, as well as the Chinese Remainder Theorem, but to no success.

I would appreciate any insight on the matter.

Thank you!

  • 1
    $\begingroup$ Consider the case that $(𝑝−1)$ and $(𝑞−1)$ are divisible by 3? What do you see? $\endgroup$
    – kelalaka
    Jan 24 at 9:17
  • 1
    $\begingroup$ In this case, if we restate $b^3 \equiv a\ (mod\ p)$ and $b^3 \equiv a\ (mod\ q)$ due to the Chinese Remainder Theorem. We can let $x \equiv b^{(p-1)/3}$ and $y \equiv b^{(q-1)/3}$, the exponents are integers by our assumption, and we could claim that there are exactly 3 solutions for $b$ in the range $[0, p-1]$ and $[0, q-1]$. By the Chinese Remainder Theorem there would be exactly 9 solutions for $b$ in the range $[0, pq-1]$. But that doesn't help me find what is the case where they AREN'T divisible by 3. $\endgroup$ Jan 24 at 9:45
  • 2
    $\begingroup$ Hint: when $p-1$ is not divisible by $3$, show that there are positive integers $d_p$ such that $3\,d_p\equiv1\pmod{p-1}$. Try to raise to such power $d_p$ both sides of the equation $b^3\equiv a\pmod p$ (that was rightly obtained thru the CRT), and use Fermat's little theorem. For (virtual) bonus points: more generally, for how many integers $a$ in $[0,n)$ does there exist $b$ for which $b^3\equiv a\pmod n$ ? You are welcome to write an answer to your own question. $\endgroup$
    – fgrieu
    Jan 24 at 10:13
  • 1
    $\begingroup$ BTW: terminology nit: the group $\mathbb{Z}_n^*$ (where $n$ has two distinct odd factors) is not cyclic; there is no single element that generates the entire group. $\endgroup$
    – poncho
    Jan 24 at 14:48
  • $\begingroup$ katz/lindel's proof of #QR_n in chapter 13.4.1 (second ed.) should help $\endgroup$
    – Grifball
    Jan 24 at 22:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.