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

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!

• Do you know about primitive roots $\pmod p$? – lulu Nov 10 '18 at 10:29
• Hmm, I don't believe so – Stawbewwy Nov 10 '18 at 10:44
• Well, that theory makes your specific problem easy...$x^3-1\equiv 0\pmod p$ has a solution iff $3\,|\,p-1$. But, generally speaking, it is not easy to find the roots of a general polynomial, even $\pmod p$. – lulu Nov 10 '18 at 10:46
• Your example $x^3-1\equiv0$ is not a great one, since it has an obvious solution $x\equiv1$. – Angina Seng Nov 10 '18 at 10:51
• We could just say $x^3 - c$ in general. Also thank you Lulu, I'll take a look at it :) – Stawbewwy Nov 10 '18 at 18:43

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.