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!

  • $\begingroup$ Do you know about primitive roots $\pmod p$? $\endgroup$ – lulu Nov 10 '18 at 10:29
  • $\begingroup$ Hmm, I don't believe so $\endgroup$ – Stawbewwy Nov 10 '18 at 10:44
  • $\begingroup$ 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$. $\endgroup$ – lulu Nov 10 '18 at 10:46
  • $\begingroup$ Your example $x^3-1\equiv0$ is not a great one, since it has an obvious solution $x\equiv1$. $\endgroup$ – Angina Seng Nov 10 '18 at 10:51
  • $\begingroup$ We could just say $x^3 - c$ in general. Also thank you Lulu, I'll take a look at it :) $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ Thanks for the answer! $\endgroup$ – Stawbewwy Nov 10 '18 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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