# On number of roots mod $p$ of a polynomial with integer coefficients

Let $F(x)$ be a polynomial with integer coefficients of degree $D$. I know that this polynomial has at most $D$ roots modulo $p$, where $p$ is prime. One way of achieving this is using division algorithm over finite fields. I was wondering if anyone could tell me a proof which is even more elementary so that I can prove this without going into finite fields? Thank you very much!

This can be proved by induction.

The base case where $D=1$ is simple.

Assume the claim is true for $D-1$.

If $F(x)$ which has a degree of $D$ has no solutions, our proof is done.

If it has at least one solution, let this solution be $q$.

$F(x)\equiv (x-q)g(x) \pmod p$ where $g(x)$ is a polynomial with a degree of $D-1$ .

Assume that another solution $r$ that is not $q$ has to be a solution to $g(x)$. This is because $p$ is prime, and $\gcd(q-r,p)=1$.

There are at most $D-1$ solutions to $g(x)$, so if we consider $q$ as well, we conclude there are atmost $D$ solution to $f(x)$.

Here's a hint for a proof that doesn't use finite fields nor the fact that the coefficients of $$F$$ are integer:

definition an integer $$r$$ is a root modulo $$p$$ of $$F$$ iff $$\exists k \in \mathbb{Z}, \, F(r) = k p$$.

EDIT There's a problem with this definition since if $$r$$ is a root modulo $$p$$ of $$F$$ then $$r + z p$$ is also a root modulo $$p$$ of $$F$$ for any $$z \in \mathbb{Z}$$ ! We hence have to change the formulation slightly : we show that there are at most $$D$$ equivalence classes modulo $$p$$ of roots modulo $$p$$.

If $$F$$ has a root modulo $$p$$, say $$r$$, then there's some integer $$k_r$$ such that $$F(r) = k_r p$$. Now, the polynomial $$F_r :=F - k_r p$$ has the same roots modulo $$p$$ as $$F$$ :

indeed, let $$r'$$ be a root modulo $$p$$ of $$F$$, ie there exists an integer $$k_{r'}$$ such that $$F(r') = k_{r'} p$$. Now we see that $$r'$$ is a root modulo $$p$$ of $$F_r$$ since :

$$F_r(r') = (k_{r'} - k_r) p$$ Likewise, any root modulo $$p$$ of $$F_r$$ is also a root modulo $$p$$ of $$F$$.

But $$r$$ is a true root of $$F_r$$, we can hence find $$G$$, of degree $$deg(F) - 1$$ such that $$F_r = (X -r) G$$

Any other root modulo $$p$$ of $$F_r$$ (hence of $$F$$) is also equivalent modulo $$p$$ to a root modulo $$p$$ of $$G$$. Do you see how to start a recurrence from there on?

This is not about finite fields at all, since this holds for all fields. The easiest proof is the one you mention: Any root gives rise to a linear factor. We can divide by that factor to decrease the degree by one and then use induction.

By passing to the quotient field, one easily sees that the claim also holds for any integral domain. But the claim is false for arbitrary rings, as $X^2-1 \in (\mathbb Z/8\mathbb Z)[X]$ shows. You should carefully think about the question, where precisely the proof fails if the ring is not a domain.