For which primes p will there be a solution to $x^3 + 1 ≡ (\mod p) $other than $x ≡ - 1 (\mod p)$

Question

I'm trying to learn more about modular arithmetic by practicing some problems, but I'm having some difficulty with this one.

For which primes p will there be a solution to $x^3 + 1 ≡ (\mod p)$ other than $x ≡ - 1 (\mod p)$?

I'm given a hint that there must be primitive roots mod p, and if a is a primitive root mod p we know the smallest positive integer $k$ for which $a^k ≡ -1 (\mod p)$. But I'm not sure how that helps me find a solution other than $x = -1 (\mod p)$.

Could anyone help me with this problem?

Thanks!

Answer 1

Hint: Try with $p = 7$ and $p = 5$ (both happen to have $3$ as primitive root, which you should check to be sure), find the order of the primitive root in each case. Use that order to see what powers of $3$ solves the equation.

Looking at your results after trying the above, what exactly is it with $p = 7$ that allows multiple solutions, while $p = 5$ fails to have them? Now generalize.

Answer 2

Another hint:

Factor the equation $$ x^3+1=(x+1)(x^2-x+1)=0 $$

The quadratic factor must have two roots distinct from $-1$, which implies $p>3$. The discriminant $-3$ has to be a non-zero square. Use the law of quadratic reciprocity.

Answer 3

$\newcommand{\Z}{\mathbb{Z}}$Let $F = \Z / p \Z$, with $p$ a prime. Consider the polynomial $$ g = x^{6} - 1 = (x^{3} - 1) (x^{3} + 1) = (x^{3} - 1) (x + 1) (x^{2} - x + 1) \in F[x]. $$ You want to know when $$f = x^{2} - x + 1$$ has a root in $F$ different from $-1$.

Clearly you must have $p \ne 2$ then, otherwise the only possible root of $f$ in $F$ is $1 = -1$, and $f(1) = 1^{2} - 1 + 1 = 1 \ne 0$.

Also, you want $p \ne 3$, as noted in another answer, because if $p = 3$ the polynomial $x^{2} - x + 1 = x^{2} + 2 x + 1 = (x + 1)^{2}$ has only $-1$ as a root.

So we have $p > 3$.

Now a root $\alpha$ of $f$ is a root of $g$, and thus $\alpha^{6} = 1$. So $\alpha$ has multiplicative order a divisor of $6$, thus one of $1, 2, 3, 6$.

As $f(1) = 1 \ne 0$, we have $\alpha \ne 1$.

As $\alpha \ne -1$, we have $\alpha^{2} \ne 1$.

Also, since $0 = f(\alpha) = \alpha^{2} - \alpha + 1$, we have $\alpha^{2} = \alpha - 1$. It follows that $\alpha^{3} = \alpha \alpha^{2} = \alpha (\alpha - 1) = \alpha^{2} - \alpha = -1 \ne 1$, so $\alpha^{3} \ne 1$.

We have shown that $\alpha$ does not have order $1, 2, 3$. Thus $\alpha$ has order $6$.

So a necessary condition is for the multiplicative group $F^{*}$ to have an element of order $6$, that is $6 \mid p - 1$, or $$p \equiv 1 \pmod{6}.$$ Since $F^{*}$ is cyclic, this is also a sufficient condition.

Answer 4

Another approach. Suppose that $p$ has the form $6k+5$, with $k$ an integer. Then, by Fermat's little theorem, for $c$ any non-zero residue modulo $p$, \begin{align*} c&=c^{6k+5}\\ \implies c^2&=c^{12k+10}\\ \implies c&=c^{12k+9}=(c^{4k+3})^3, \end{align*} so $c$ is a cube. In addition, $0^3=0$. Thus, by the pigeonhole principle, the cubes of all residues are distinct, so no residue $x$ except $-1$ can have $x^3=-1\mod p$.

Answer 5

Since $\,a\,$ is a primitive root there are $\,j,k\,$ with $\, x \equiv a^{\large j}\,$ and $\, {-}1 \equiv a^{\large k}\,$ hence $$x^{\large 3}\equiv -1\iff a^{\large 3j}\equiv a^{\large k}\iff 3j\equiv k\!\!\!\pmod{\!p-1}$$

This has a unique solution $\,j\equiv 3^{-1}k\pmod{p-1}$ $\iff 3\nmid p-1$ so there's a solution besides $\,x\equiv -1\iff p\equiv 1\pmod{\!3}\iff p\equiv 1,4\pmod{\!6}.\,$ But $\,p\neq 4+6n\,$ by $\,p\,$ odd.