Prove that $x^3 \equiv a \pmod{p}$ has a solution where $p \equiv 2 \pmod{3}$?
How can I prove a congruence equation has a solution? I tried to link Fermat's little theorem with this problem, but I couldn't find a way to solve it.
My attempt was:
$$x^3 \equiv 1 \pmod{2}$$
$$x^3 \equiv a \pmod{p}$$
If $p \equiv 2 \pmod{3}$, I have $p = 3k + 2$, for some integers $k$. But I was stuck here :(. Any idea?
Another question is, is there are infinitely many primes of the form 3k + 2?
A hint would be sufficient.
Thanks,
Thanks,
Best Answer
Hint $\:$ Show $ \: x\to x^3\: $ is a bijection via $\rm\color{#c00}{little\ Fermat}$ and $\, \overbrace{3 (2K\!+\!1) = 1 + 2(3K\!+\!1)}^{\textstyle 3J\ \equiv\ 1\ \pmod{p-1}}$
In detail: $ \ \ x^{3J} =(x^{\color{#0a0}{2K+1}})^{\large 3}=\ x (\color{#c00}{x^{3K+1}})^{\large 2} \equiv x\pmod{\!p}\ \ $ for $ \ x\not\equiv 0,\, $ prime $\,p = 3K\!+\!2$.
Thus $ \ x\to x^3\ $ is onto on the finite set $ \:\mathbb Z/p\:,\:$ so it is also $\,1$-$1,\,$ i.e. $ \ x^3 \equiv y^3\, \Rightarrow\, x\equiv y$.
Note: this answers the original version of your question (existence and uniqueness of cube roots).
Remark $ $ the exponent $\,J = \color{#0a0}{2K\!+\!1}$ with $\,x^{3J}\equiv x^{\large 1}\pmod{p=3K\!+\!2}\,$ was computed via
$\!\bmod p\!-\!1=3K\!+\!1\!:\ \ 3J\equiv 1\iff J\equiv \dfrac{1}{3}\equiv \dfrac{-3K}3\equiv -K\equiv \color{#0a0}{2K+1}$
using modular order reduction and $\bmod p\!:\ x^{\large p-1}\equiv 1,\ x\not\equiv 0,\,$ by little Fermat.