How to determine if a polynomial has roots modulo a prime?
I was attempting to find solutions to this polynomial $x^3+x^2-4\equiv 0$ mod($7$)
The only method I currently know to determine solutions is to try every element in the complete residue system. There are none.
However given $x^3+x^2-4\equiv 0$ mod($10007$), ($10007$ is a prime)
I would have no idea how to find roots of this polynomial or if they even exist.
Best Answer
One way to count the solutions for $f(x)\equiv0\pmod p$ (where $p$ is prime) is to compute the gcd of $f(x)$ and $x^p-x$ over the field $\Bbb F_p$ of $p$ elements. This gcd is $g(x)=\prod_{a\in R}(x-a)$ where $R$ is the set of roots of $f$ in $\Bbb F_p$.
This may seem daunting if $p$ is large. But as long as $f$ has small degree one can start by reducing $x^p-x$ modulo $f(x)$ over $\Bbb F_p$. Doing the $x^p$ modulo $f(x)$ is just like computing $a^k$ modulo $m$ for large $m$ and can be done by the binary powering algorithm.