4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Which $a$ is not a cube in this case? $\endgroup$ – lhf Mar 20 '14 at 3:26
  • 1
    $\begingroup$ @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. $\endgroup$ – user2345215 Mar 20 '14 at 3:29
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.