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

Question

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.

Thanks for your help

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.