Solve $x^3 \equiv 1 \pmod p$ for $x$

How can I find solution for $x^3 \equiv 1 \pmod p$ ($p$ a prime) efficiently?

Trivial root is $x_1 = 1$. I need to find other roots $x_2, x_3$.

Solution 1:

The integers modulo $p$ form a field. Since $x^3 - 1 = (x-1)(x^2+x+1)$, the problem is equivalent to solving $x^2+x+1\equiv 0 \pmod{p}$. For $p\neq 2$, the usual quadratic formula works; so you would need to find $y$ such that $y^2\equiv -3\pmod{p}$. If $p=2$, then $x^2+x+1=0$ has no solutions, and if $p=3$, then $x^3-1 = (x-1)^3$, so again there is no root other than $x=1$.

Let's consider the other primes, $p\gt 3$.

Using quadratic reciprocity, if $p\equiv 1\pmod{4}$, then $-1$ is a square modulo $p$ and we have: $$\left(\frac{-3}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right).$$ So if $p\equiv 1 \pmod{3}$ (hence $p\equiv 1 \pmod{12}$) then $-3$ is a square modulo $p$; if $p\equiv 2\pmod{3}$ (so $p\equiv 5\pmod{12}$), then $-3$ is not a square modulo $p$, so there is no other solution.

If $p\equiv 3\pmod{4}$, then $-1$ is not a square modulo $p$, and we have: $$\left(\frac{-3}{p}\right)=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)$$ (since $\left(\frac{3}{p}\right) = -\left(\frac{p}{3}\right)$); again, if $p\equiv 1\pmod{3}$ (so $p\equiv 7\pmod{12}$) then $-3$ is a square modulo $p$; and if $p\equiv 2\pmod{3}$ (so $p\equiv 11\pmod{12}$) then $-3$ is not a square modulo $p$.

In summary, there are roots of $x^3-1$ modulo $p$ other than $x\equiv 1\pmod{p}$ if and only if $p\equiv 1\pmod{6}$. If $p=6k+1$ is such a prime, then the two roots of $x^3-1$ other than $x=1$ are precisely the roots of $x^2+x+1$, which are $$\frac{-1\pm\sqrt{-3}}{2} = -3k(-1\pm a),$$ where $a$ is an integer such that $a^2\equiv -3\pmod{p}$. This means you still need to figure out the square root, which can be done using any of the methods suggested by Bill Dubuque, such as Tonelli's algorithm (say, in Shanks' version as described in Wikipedia).

Added: As Alex Bartel notes in comments and in his own answer, one can avoid the use of quadratic reciprocity above. Since the units of $\mathbb{Z}/p\mathbb{Z}$ form a cyclic group of order $p-1$, there are nontrivial solutions to $x^3=1$ if and only if $3$ divides the order, that is, if and only if $p\equiv 1\pmod{3}$. From there, it is an easy jump to solutions if and only if $p\equiv 1 \pmod{6}$, since otherwise we would have $p\equiv 4\pmod{6}$ which is impossible since $p$ is prime. Once one establishes that, the quadratic formula can be applied safe in the knowledge that these primes must have $-3$ as a quadratic residue.

Solution 2:

First, note that if $p \equiv 2\text{ mod } 3$, then raising to the third power is a bijection on $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, so that 1 is the only root. If $p \equiv 1\text{ mod } 3$, then the only way I can think of to find the roots is to find a primitive root modulo $p$ (i.e. a generator of the cyclic group $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$) and take it to the powers $(p-1)/3$ and $2(p-1)/3$.