0
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $k^{2p-1}\equiv k^p\cdot k^{p-1}\equiv k\cdot k^{p-1}\equiv k^p\equiv k\bmod p$ $\endgroup$ – J. W. Tanner Jun 24 at 20:07
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Jun 24 at 19:05
1
$\begingroup$

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.

| cite | improve this answer | |
$\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.