# 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!

$$\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.

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.

• I managed to confirm that 5 and 7 both have 3 as a primitive root, with order for p = 5 as 4 and the order for p = 7 as 6. From here, I tried to find the values of 3^order mod 5 and mod 7, but I seem to get different answers in both cases. Could you please guide me a bit further on this problem? Thanks! – Kami May 7 at 8:45
• @Kami For $p = 7$, with the order of the primitive root being $6$, what are the possible orders of powers of the primitive root? And what about for $p = 5$? And if we want additional solutions to $x^3-1\equiv 0$, what orders should we look for? – Arthur May 7 at 8:51
• For p = 7, I get 1 and 2 as the orders of the powers of the primitive root. For 4 as the order when p = 5, I also get values as 1, 2. So for x^3 - 1, we would have to look for orders ≠ 1,2? I don't know much about this topic so I'm quite confused. Sorry for the trouble! – Kami May 7 at 9:07
• @Kami For $p=7$, what is the order of $3^2$? And in both cases, your list is missing the order of $3$ itself. – Arthur May 7 at 9:12

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.

• I'm not familiar with the law of quadratic reciprocity, could you please elaborate on how to continue solving this problem? Thanks! – Kami May 7 at 8:43
• Do you know the Legendre symbol? – Bernard May 7 at 8:51

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$$.

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.