Prove that $x^3 \equiv a \pmod{p}$ has a solution where $p \equiv 2 \pmod{3}$?

Question

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,

Answer 1

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.

Answer 2

For reference, check out Ireland and Rosen's A Classical Introduction to Modern Number Theory, which will allow you a first taste on a bunch of topics in number theory (though the authors assume basic familiarity with abstract algebra). What's nice about your question is that it admits several methods of proof.

Notice that your hypothesis on $p$ is unnecessary if $a \equiv 0 \pmod{p}$ (simply use $x=0$). So assume $a \not\equiv 0 \pmod{p}$. In that case, Ch.4 of Ireland and Rosen tells us that (1) $a^{p-1} \equiv 1 \pmod{p}$ and (2) $x^3 \equiv a \pmod{p}$ is solvable if and only if $$a^{(p-1)/\gcd(p-1, 3)} \equiv 1 \pmod{p}.$$ But guess what: since $p-1 \equiv 1 \pmod{3}$ by hypothesis, congruence theory says $$\gcd(p-1, 3) = \gcd(1, 3) = 1.$$ Thus by (1), $$a^{(p-1)/\gcd(p-1, 3)} = a^{p-1} \equiv 1 \pmod{p},$$ and so we're done!

Answer 3

My intuition tells me to attempt a proof by contradiction via factoring: Assume $x^3 \equiv y^3 \equiv a \pmod p$ thus $(x-y)(x^2+xy+y^2) = x^3-y^3 \equiv 0$. Since $\mathbb{Z}_p$ is an integral domain and we are assuming $x$ and $y$ are distinct (as elements of $\mathbb{Z}_p$, we must have $x^2+xy+y^2 \equiv 0$, thus $x^2+xy+y^2 = n(3k+2)$ for some $n$. If $n$ is even we have that every term is even, which allows us to factor out $2$ from $x$ and $y$. We can assume this is true since if $x$ is an odd solution, $x+3k+2$ is an even solution as operations on $\mathbb{Z}_p$ are well-defined, and similarly for $y$. Thus we have $x/2$ or $(x+3k+2)/2$ and $y/2$ or $(y+3k+2)/2$ are solutions. You should be able to derive a contradiction from there.

Answer 4

You can verify directly, using Fermat's little theorem, that $x=a^{(2p-1)/3}$ is a solution to $x^3\equiv a\pmod p$ (and $(2p-1)/3$ is an integer since $p\equiv2\pmod 3$).

(Coming up with this solution is not quite as easy as verifying it, to be sure. Because of the existence of a primitive root $g$ modulo $p$, proving that $x^3\equiv a\pmod p$ always has a solution is equivalent, thanks to the change of variables $a = g^c$ and $x=g^b$, to proving that $3b \equiv c \pmod{p-1}$ always has a solution. This latter congruence has the solution $b\equiv 3^{-1}c = \frac{2p-1}3 c\pmod {p-1}$. Here the case $a\equiv0\pmod p$ should be treated separately.)

There are infinitely many primes of the form $3k+2$, that is, infinitely many primes that are congruent to $2\pmod 3$. See Dirichlet's theorem or the prime number theorem for arithmetic progressions.