1
$\begingroup$

Using p ≡ -1 (mod 3) and p is prime, how can you show $a^3≡b$ (mod p) iff $a≡b^d$ (mod p)? This shows integers mod p has a unique cubic root.

3d ≡ 1 (mod p-1)

I'm not sure where to begin... Does anyone know?

Thanks

$\endgroup$
  • $\begingroup$ What does "integers has a unique cubic root" mean? All the integers or what integers, or where...or what? And what is $\;d\;$ there? $\endgroup$ – Timbuc Dec 1 '14 at 4:12
  • $\begingroup$ You forgot to say what $d$ is. Which part are you having trouble with? Showing the "iff" part? Or showing that it implies uniqueness of cube root? Or something else? $\endgroup$ – Hurkyl Dec 1 '14 at 4:12
  • $\begingroup$ Pretty much all of it. $\endgroup$ – omega Dec 1 '14 at 4:13
  • 1
    $\begingroup$ One direction, $b^d\equiv a^{3d}=a^{(k)(p-1)+1}\equiv a^1\pmod{p}$. The question will probably be closed while I try to type the full answer, so you will have to take care of the other direction. Not hard. $\endgroup$ – André Nicolas Dec 1 '14 at 6:11
  • 1
    $\begingroup$ There is by the way a more natural way to prove the ultimately desired result. Show the cube function mod $p$ is one to one by showing that if $a^3\equiv a_1^3$ then $a\equiv a_1$. Let $c_1$ be the inerse of $a_1$. Then $(ac_1)^3\equiv 1$, so the order of $ac_1$ is $3$ or $1$. But $3$ does not divide $p-1$. $\endgroup$ – André Nicolas Dec 1 '14 at 6:23
1
$\begingroup$

Let $p$ be a prime that is congruent to $-1$ modulo $3$. Then $3$ does not divide $p-1$. It follows that there is a positive integer $d$ such that $$3d\equiv 1\pmod{p-1}.\tag{1}$$

We show that for any $a$ and $b$, and any positive $d$ that satisfies (1), we have $$a^3\equiv b\pmod{p}\quad\text{if and only if}\quad a\equiv b^d\pmod{d}.$$ The result is obvious if one of $a$ or $b$ is divisible by $p$. So we may assume that $a$ and $b$ are each relatively prime to $p$.

Suppose that $a^3\equiv b\pmod{p}$. Then $(a^3)^d\equiv b^d\pmod{p}$. But $3d\equiv 1\pmod{p-1}$. So $3d=(p-1)k+1$ for some integer $k$. It follows that $$b^d\equiv a^{3d}=(a^{p-1})^k a^1\equiv a\pmod{p}.$$ In the above calculation, we used Fermat's Theorem to show that $a^{p-1}\equiv 1\pmod{p}$.

For the other direction, suppose that $a\equiv b^d\pmod p$. We want to show that $a^3\equiv b\pmod{p}$. We use the fact that $3d$ is of the shape $(p-1)k+1$. We have $$a^3\equiv b^{3d}=(b^{p-1})^kb^1\equiv b\pmod{p}.$$

Remark: If $p\equiv -1\pmod{3}$, a suitable $d$ is quickly computed, even for large $p$, by using the Euclidean Algorithm. Now given any $b$, we can compute cheaply the modular cube root $a$ of $b$ by calculating the remainder when $b^d$ is divided by $p$. This too can be done efficiently, by using the "binary" method for exponentiation.

So not only does the modular cube root of $b$ exist, it can also be efficiently computed. The story is more messy if $p\equiv 1\pmod{3}$. In that case, only one-third of the numbers is the interval $1\le b\le p-1$ have modular cube roots, and finding one, when it exists, is computationally more complicated for large $p$.

$\endgroup$
  • $\begingroup$ I recognize this is old, but why does it follow in line 2 that such a positive integer d exists? I can see why one would exist with 3d≡2 mod p-1, but not one with 3d≡1 $\endgroup$ – MathTrain Apr 25 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.