# Three different numbers with x³=x mod p

p is a prime greater than 2 and $a \in \mathbb{Z}_p$. Why are there exactly three solutions for a³ = a mod p? Obviously 0 and 1 are both in $\mathbb{Z}$ and valid solutions, but that still means, there is one element (and only one) missing. I can't figure out which one and neither do I understand why there could not be more valid solutions. Any tips?

Unless otherwise stated, $a$ is any integer representative of an eponymous element of $\mathbb{Z}_p$. \begin{align} a^3\equiv a\pmod p &\Longleftrightarrow a^3-a\equiv0\pmod p\\ &\Longleftrightarrow a\cdot(a^2-1)\equiv0\pmod p\\ &\Longleftrightarrow a\cdot(a-1)\cdot(a+1)\equiv0\pmod p\\ &\Longleftrightarrow\begin{cases} a\equiv0\pmod p&\text{ or}\\ a-1\equiv0\pmod p&\text{ or}\\ a+1\equiv0\pmod p \end{cases}\end{align} The last step uses that since $p$ is prime, if it divides the product of some integers [here: $a$, $a-1$, and $a+1$ ], then it must divide at least one of these integers. The reverse trivially holds without the hypothesis that $p$ is prime.

Since $p$ is greater than $2$, the three solutions $a\equiv0\pmod p$, $a\equiv1\pmod p$, $a\equiv p-1\pmod p$ are distinct elements of $\mathbb{Z}_p$.

Without the hypothesis that $p$ is prime, there can be additional solutions to $a^3\equiv a\pmod p$; for example, $a^3\equiv a\pmod{15}$ holds for nine out of fiteen elements $a$ of $\mathbb{Z}_{15}$.

Keep in mind that $x\equiv0\pmod p$ means exactly the same as: $p$ divides $x$.

Thanks to CGFoX for having corrected the $a\cdot(a^2-1)$ expression.

• One more thing: Not every third degree polynomial has three solutions in groups or finite fields. For example, $a^3-1 = 0$ has only then three solutions, if $\phi(p)$ is a multiple of $3$, because otherwise the function $f(x)=x^3$ mod $p$ is a bijection and $1$ has only one root. In the given equation it doesn't depend on $p$, because the solution $a=0$ is a given and $1$ has always two square roots (and $\phi(p)$ is always a multiple of $2$) – tylo Jun 6 '14 at 12:23

The missing solution is $p-1$. This is a polynomial of degree 3, so (assuming $p$ is prime) it can have at most 3 roots. This polynomial in particular has exactly 3 roots (again, assuming $p$ is prime): you can factorize it to $a(a^2-1)=0 \pmod p$, so the roots are $a=0$ and the two roots of $a^2-1$, which are 1 and $-1 \bmod p=p-1$.

• This shows there are at least three solutions, not exactly three solutions. In an arbitrary ring, it does not hold that any polynomial of degree $n$ has at most $n$ roots. You need to invoke the hypothesis on $p$ somehow. – fgrieu Jun 5 '14 at 18:37
• The above comment was for rev1. $\;$ Call me picky but "This" in the second sentence can only refer to $p−1$, which is not a polynomial of degree 3 [ $a^3-a$ is the polynomial "This" is intended to designate]. $\;$The improved [rev2](crypto.stackexchange.com/revisions/16572/2) still does not tell how "$p$ is prime" implies that a polynomial of degree 3 has at most 3 roots;$\;$ nor why there are exactly 3 roots, which BTW does not hold for quite all primes $p$ as stated [we need to invoke "greater than 2" in the statement]. – fgrieu Jun 5 '14 at 23:18