# For every $k \in \Bbb Z$ there is $0 \le x \le p-1$ such as $x^3\equiv k \pmod {p}$

This question is looking like an easy one but I have been trying to solve it for the last couple days and I haven't been able to prove it - so I need some help.

The question: Let $$p$$ be a prime number, $$p\equiv 5 \pmod{6}$$ prove that for every $$k \in \Bbb Z$$ there is $$0 \le x \le p-1$$ such as $$x^3\equiv k \pmod{p}$$.

I thought to prove it with induction but it didn't work, although I still sure this is the right way.

• Use \pmod{p} to get the parenthetical version of the mod operator, in correct typeface. – Arturo Magidin Jun 24 at 18:45
• Thank you for your edit ;) – The student Jun 24 at 19:00

If $$k \bmod p=0$$, then $$x=0$$ is a solution to $$x^3\equiv k\pmod p$$.

Otherwise, can you show that $$x=k^{(2p-1)/3} \bmod p$$ is a solution?

(Note that $$p\bmod6=5\implies p\bmod3=2\implies (2p-1)/3$$ is an integer.)

• $k^{2p-1}\equiv k^p\cdot k^{p-1}\equiv k\cdot k^{p-1}\equiv k^p\equiv k\bmod p$ – J. W. Tanner Jun 24 at 20:07

Hint. The multiplicative group of nonzero elements modulo $$p$$ has order $$p-1\equiv 4\pmod{6}$$, hence is of the form $$6k+4$$. Show this means that $$r\mapsto r^3$$ is a bijection in that group.

You have $$3 \nmid (p-1)$$. As $$p$$ is a prime, it must have primitive roots. Let $$g \bmod{p}$$ be a primitive root modulo $$p$$, we claim that $$g^3$$ is also a primitive root.

Let $$d$$ be the order of $$g^3$$. Then, $$g^{3d} \equiv 1 \pmod{p} \implies (p-1) \mid (3d) \implies (p-1) \mid d$$ as $$p-1$$ and $$3$$ share no factors. As $$d \mid (p-1)$$ by Fermat's Little Theorem, $$d=p-1$$ showing that $$g^3$$ is a primitive root.

Now, every $$k \in \mathbb{F}_p$$ can be written as $$g^{3n}=(g^n)^3$$ modulo $$p$$.

• You don’t actually need a primitive root; the argument goes through for any abelian group whose order is not a multiple of $3$, even if it is not cyclic. – Arturo Magidin Jun 24 at 19:05

Hint: If $$p=6t+5$$, then $$1+2(p-1)=3(4t+3)$$. Use Fermat's theorem to prove that $$x \mapsto x^3$$ is surjective.