Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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 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$.

share|improve this answer
2  
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 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 at 23:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.