Elementary Number Theory - Determining if there exist roots for a polynomial congruence with a prime modulus

Question

If we consider something like the polynomial $f(x) = x^3-1$, and we want to know if there exists any solutions at all for $x^3 - 1 \equiv 0 \ (mod \ p)$, where $p$ is prime, is there a way to answer this without just plugging in every possible value of $x$? (i.e, $0,1,...,m-1$). From my class, we learned that if $p$ is a prime, and assuming there exists a coefficient of a term in $f(x)$ who $p$ does not divide, the congruence has at most $n$ solutions, where $n$ is the degree of the highest degree term , $cx^a$, such that $p \nmid c $. I've read about some particular examples, like with a quadratic, there are solutions if and only if the discriminant is a square modulo p. For linear congruence's, we do know that there is a simple way to check if there are any solutions at all, which is basically like checking if a linear Diophantine equation has any solutions. I am wondering if there is a general way to extend the question of "do there exist any roots" to any polynomial. A result like this would be delightful to speed-up the process of finding roots when solving congruence's for polynomials. Thanks!

Answer 1

To determine whether $f(x)\equiv0\pmod p$ has solutions where $p$ is prime, compute $\gcd(f(x),x^p-x)$ over the field $\Bbb Z_p$ of integers modulo $p$. This can be done by the Euclidean algorithm for polynomials. The answer you get will be a polynomial $h(x)$ whose roots are the roots of $f$ lying in $\Bbb Z_p$, since $x^p-x=0$ has precisely the elements of $\Bbb Z_p$ as roots.

As long as the degree $d$ of $f$ is small, this can be done efficiently. The first step of the Euclidean algorithm might seem to pose problems, as it requires finding the remainder when dividing $x^p-x$ (which may have large degree) by $f(x)$. But this boils down to computing $x^p-x$ in the quotient ring $\Bbb Z_p/(f(x))$ and computing $x^p$ therein can be done efficiently by the binary squaring method.