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