For which primes p will there be a solution to x^3 + 1 ≡ (mod p) other than x ≡ - 1 (mod p) 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!
 A: $\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.
A: 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.
A: 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.
A: 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$.
A: 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.
