Let $p$ be a prime and $p \geq 5$, Consider the congruence $x^3 \equiv a$ (mod p) with $\gcd(a,p)=1$. Show that The congruence has either no solution or three incongruent solutions modulo $p$ if $p \equiv 1$ (mod 6) and has unique solution modulo $p$ if $p \equiv 5$ (mod 6).
My attempt: By Lagrange theorem, the congruence $x^3 \equiv a$ (mod p) has at most $3$ incongruent solutions modulo $p$. Suppose the congruence has a solution $b$ such that $b^3 \equiv a$ (mod p). Then $x^3 \equiv a \equiv b^3 \textit{mod p} \Rightarrow x^3 -b^3 \equiv 0$ (mod p). Note that $x^3 -b^3=(x-b)(x^2+bx+b^2)$
Now I stuck at here. I observe that if $p \equiv 1$ (mod 6), then $(x^2+bx+b^2) \equiv 0$ (mod p) has two incongruent solutions modulo $p$ and if $p \equiv 5$ (mod 6), then $(x^2+bx+b^2) \equiv 0$ (mod p) has one unique solution modulo $p$.
Can anyone guide me?
Best Answer
We give an extremely detailed argument. Sorry about the length!
Suppose first that $p\equiv 1\pmod{6}$. So $p=6k+1$ for some $k$.
We will use a primitive root argument. Let $g$ be a primitive root of $p$. In group-theoretic terms, let $g$ be a generator of the multiplicative group modulo $p$.
Then $g$ has order $p-1$ modulo $p$. Note that $g^{p-1}=(g^{2k})^3\equiv 1\pmod{p}$ by Fermat's Theorem. Also, $(g^{4k})^3\equiv 1\pmod{p}$. Neither $g^{2k}$ nor $g^{4k}$ is congruent to $1$ modulo $p$, since the order of $g$ is $6k$. And they are not congruent to each other.
Thus the congruence $z^3\equiv 1\pmod{p}$ has at least $3$ (and therefore exactly $3$ solutions, namely $1$, $g^{2k}$, and $g^{4k}$.
So if $b^3\equiv a\pmod{p}$, then we also have $(g^{2k}b)^3\equiv a\pmod{p}$ and $(g^{4k}b)^3\equiv a\pmod{p}$. It follows that the congruence $x^3\equiv a \pmod{p}$ has $3$ solutions if it has a solution.
Now suppose that $p\equiv 5\pmod{6}$. Let $p=6k+5$. Let $x$ and $y$ be non-zero integers, and suppose that $x^3\equiv y^3\pmod{p}$. This is the case if and only if $(xy^{-1})^3\equiv 1\pmod{p}$. We show that this forces $x\equiv y\pmod{p}$.
To do this, it is enough to show that the congruence $z^3\equiv 1\pmod{p}$ has only the obvious solution $z\equiv 1\pmod{p}$.
Again let $g$ be a primitive root of $p$. Any $z$ is congruent to $g^m$ for some $m$ with $1\le m\le p-1$. Ig $z^3\equiv 1\pmod{p}$ then $g^{3m}\equiv 1\pmod{p}$. It follows that $3m$ divides the order of $g$, that is, $3m$ divides $6k+4$. Since $3$ and $6k+4$ are relatively prime, it follows that $m$ divides $6k+4=p-1$. Thus $g^m\equiv 1\pmod p$, and therefore $z\equiv 1\pmod{p}$.
Now consider the mapping $\psi$ that takes any number $x$ between $1$ and $p-1$ into the remainder when $x^3$ is divided by $p$. By the calculation above, the function is one to one (injective). A one to one function from a finite set to itself must be onto (surjective). It follows that every number between $1$ and $p-1$ is $\psi(x)$ for some $x$. This says that every number between $1$ and $p-1$ is congruent to $1$ modulo $p$. That is what we wanted to prove.