# How to prove integers has a cubic root mod p?

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

• What does "integers has a unique cubic root" mean? All the integers or what integers, or where...or what? And what is $\;d\;$ there? – Timbuc Dec 1 '14 at 4:12
• 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? – Hurkyl Dec 1 '14 at 4:12
• Pretty much all of it. – omega Dec 1 '14 at 4:13
• 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. – André Nicolas Dec 1 '14 at 6:11
• 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$. – André Nicolas Dec 1 '14 at 6:23

## 1 Answer

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$.

• 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 – MathTrain Apr 25 at 7:27