Let $p$ be prime. Does $x^3 \equiv a\bmod{p}$ have a solution for every $a$?

Let $p$ be prime. Does $x^3 \equiv a\bmod{p}$ have a solution for every $a$?

Here is my first idea: I know that $$x^3 \equiv a\bmod{p}$$ iff $$p\mid x^3-a$$ iff $$x^3-a=pm$$

Where $m \in \mathbb{Z}$. Then I was attempting to use the idea that now $x^3-pm=a$. I was thinking that by factoring the left side I could somehow show that there will be a solution for any $a$.

A second idea I had was to use the theorem that says the following: The congruence $ax \equiv b \bmod{n}$ has a solution iff $\gcd(a, n)\mid b$. Can I use this to rewrite the problem as $x^2x \equiv a\bmod{p}$, and then say that it will have a solution if $\gcd(x^2, p)\mid a$? And, if this approach is even possible, does it help, or should I stick to my first idea?

No. Consider $p=7$, then $2^3\equiv1^3$.

• Which $a$ is not a cube in this case? – lhf Mar 20 '14 at 3:26
• @lhf: That wasn't the question. This just shows there is one, because $0^3,1^3,\ldots,6^3$ would need to give $7$ different results. – user2345215 Mar 20 '14 at 3:29

If $p\equiv 1\pmod{3}$, then there is an $a$ which is not a cube modulo $p$. Let $r$ be a primitive root of $p$. Note that by Fermat's Theorem, we have $(r^{(p-1)/3})^3\equiv 1 \pmod{p}$ and $(r^{2(p-1)/3})^3\equiv 1 \pmod{p}$. Counting the obvious solution $w=1$, there are therefore $3$ distinct roots modulo $p$ of the congruence $w^3\equiv 1\pmod{p}$.

It follows that if $b$ is not congruent to $0$ modulo $p$, and $b$ has a cube root modulo $p$, then it has $3$ cube roots modulo $p$. It follows that $2/3$ of the numbers from $1$ to $p-1$ do not have a cube root modulo $p$.

If $p\equiv 2\pmod{3}$, then for any $a$ there is an $x$ such that $x^3\equiv a\pmod{p}$. Since $3$ and $p-1$ are relatively prime, there exist integers $x$ and $y$ such that $3x+(p-1)y =1$. Then $$a=a^1=a^{3x+(p-1)y}=\equiv (a^x)^3\pmod{p},$$ and therefore $a$ is the cube of $a^x$ modulo $p$.

The map $x\mapsto x^3$ is surjective iff it is injective since there are only finitely many classes mod $p$.

Fermat's theorem implies that the map is injective iff $3$ and $p-1$ are coprime.