Show congruence has different number of solutions if $p$ has different forms

Question

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?

Answer 1

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.

Answer 2

As $p \neq 2$ you know that $2$ is invertible modulo $p$. Let $\alpha$ be its inverse.

By completing the square we get

$$(x^2+bx+b^2) \equiv 0 \Rightarrow x^2+bx+\alpha^2 b^2 \equiv \beta^2(\alpha^2-1) \equiv \beta^2 \alpha^2 (1-4) \pmod{p}$$

Now all you have to do is study if $-3$ is a quadratic residue modulo $p$. The fact that you have to look at $p \mod 6$ comes very natural from here:

$$\left( \frac{-3}{p} \right)=\left( \frac{-1}{p} \right)\left( \frac{3}{p} \right)=(-1)^{\frac{p-1}{2}} (-1)^{\frac{p-1}{2}\frac{3-1}{2}}\left( \frac{p}{3} \right)=\left( \frac{p}{3} \right)$$

Simpler solution Note that $b \neq 0 \pmod{p}$. Then

$$x^3 \equiv b^3 \pmod{p} \Leftrightarrow (xb^{-1})^3 \equiv 1 \pmod{p}$$

Now, if $p \equiv 1 \pmod{6}$, once you prove that $y^3 \equiv 1 \pmod{p}$ has three solutions, the conclusion follows immediately.

If $p \equiv 5 \pmod{6}$, you can prove that $y^3 \equiv 1 \pmod{p}$ has unique solution. From here, it follows immediately that $x^3 \equiv b^3 \pmod{p} \Rightarrow x \equiv b \pmod{p}$. Thus, the function $f (x)= x^3$ is an one to one function $\mod{p}$, hence a bijection.

Answer 3

$$x^3\equiv a\pmod p\ \ \ \ (1)$$

Taking Discrete logarithm, wrt some primitive root $g\pmod p$ as we can prove that every prime has at least one primitive root

$3\cdot\text{ind}_gx\equiv \text{ind}_ga\pmod {p-1}\ \ \ \ (2)$

Using Linear congruence theorem, $(2),$ hence $(1)$ will be solvable if $(3,p-1)|\text{ind}_ga$

If $p=6b+5,$ where integer $b\ge0$ $\implies (3,p-1)=(3,6b+5)=(3,6b+5-3(2b+1))=(3,2)=1$

$\displaystyle (3,p)=1$ will always divide $\text{ind}_ga\forall a$ and consequently from the Linear congruence theorem, we have $(3,p)=1$ solution $\forall a$

If $p=6b+1,$ where integer $b\ge0 \implies(3,p-1)=(3,6b)=3$

$(2),$ hence $(1)$ will be solvable if $(3,p-1)=3|\text{ind}_ga$

If so, from the Linear congruence theorem, we have $(3,p)=3$ solutions if $3|\text{ind}_ga$