# Number of roots of polynomials in $\mathbb Z/p \mathbb Z [x]$

I was given this proposition but I was never able to prove it. Does anyone know how to solve this?

Let $f$ be a polynomial in $\mathbb{Z}/p\mathbb{Z}[x]$, where $p$ is prime. Then $f$ has at most $\deg f$ roots.

• The coefficient ring is contained in a field, $\Bbb Q_p$, (since $p$ is prime, $\Bbb Q_p$ is a field) of characteristic $0$ when $p$ is prime, and all characteristic $0$ polynomials are separable. (I'm using the characterization of separable as irreducible factors have no multiple roots) – Adam Hughes Jul 16 '14 at 0:17
• Alternatively, we know that there are roots out there "somewhere" (i.e. in an algebraic closure) so we can use the fact that polynomials over a field are a Euclidean domain, hence have unique factorization, and the irreducibles in an algebraically closed field are exactly the monomials. – Adam Hughes Jul 16 '14 at 0:29
• @AdamHughes: $\mathbb{Z}_p$ is already a field when $p$ is a prime. – hardmath Jul 16 '14 at 1:56
• What? Oh you mean $\Bbb Z/p\Bbb Z$, not $\Bbb Z_p$, the former is the field with $p$ elements, the latter is the $p$-adic numbers, though I know some use the latter notation for the former some times. – Adam Hughes Jul 16 '14 at 2:06

A polynomial of degree $n$ with coefficients in any field can have at most $n$ roots, because $X-\alpha$ is a factor of $f$ whenever $\alpha$ is a root, and the polynomial ring is a UFD.

As a consequence, a polynomial with coefficients in any integral domain can have at most $n$ roots: just consider the roots in the fraction field. (In fact, this property characterizes integral domains.)

• This doesn't require using that the polynomial ring is a UFD, but only the much simpler fact that $\,x - \alpha\,$ is prime $(\!\iff\!$ the coefficient ring is a domain) - see my answer. – Bill Dubuque Jul 16 '14 at 0:55

Hint $\$ If $\,f\ne 0\,$ has $\,\ge n\,$ distinct roots $\,r_i$ then inductively applying the Factor Theorem (e.g. below) shows $\,f = c(x\!-\!r_1)\cdots (x\!-\!r_n),\,$ so $\ r\ne r_i\,\Rightarrow\, f(r)= c(r\!-\!r_1)\cdots (r\!-\!r_n) \ne 0\,$ since all factors $\ne 0,\,$ and $\,\Bbb Z_p\,$ is an integral domain. Thus $\,f\,$ has at most $\,n\,$ roots.

Aternatively, $\,f(r_i)= 0 \,\Rightarrow\, x-r_i \mid f(x).\,$ Being divisible by the nonassociate primes $\,x-r_i\,$ it follows $\,f\,$ is divisible by their lcm = product, so there are at most $\,\deg(f)\,$ factors ($\leftrightarrow$ roots)

Bifactor Theorem $\$ Let $\rm\,a,b\in R,\,$ a commutative ring, and $\rm\:f\in R[x]\:$ a polynomial over $\,\rm R.\,$
If $\rm\ \color{#0a0}{a\!-\!b}\$ is $\,\color{#c00}{\rm cancelable}\,$ in $\rm\,R\,$ (i.e. not a zero-divsor)  then

$$\rm f(a) = 0 = f(b)\ \iff\ f\, =\, (x\!-\!a)(x\!-\!b)\ h\ \ for\ \ some\ \ h\in R[x]$$

Proof $\,\ (\Leftarrow)\,$ clear. $\ (\Rightarrow)\$ Applying Factor Theorem twice, while canceling $\rm\: \color{#0a0}{a\!-\!b},$

$$\begin{eqnarray}\rm\:f(b)= 0 &\ \Rightarrow\ &\rm f(x)\, =\, (x\!-\!b)\,g(x)\ \ for\ \ some\ \ g\in R[x]\\ \rm f(a) = (\color{#0a0}{a\!-\!b})\,g(a) = 0 &\color{#c00}\Rightarrow&\rm g(a)\, =\, 0\,\ \Rightarrow\,\ g(x) \,=\, (x\!-\!a)\,h(x)\ \ for\ \ some\ \ h\in R[x]\\ &\Rightarrow&\rm f(x)\, =\, (x\!-\!b)\,g(x) \,=\, (x\!-\!b)(x\!-\!a)\,h(x)\end{eqnarray}$$

Remark $\$ The theorem may fail when $\rm\ a\!-\!b\$ is not cancelable (i.e. is a zero-divisor), e.g.

$$\rm mod\ 8\!:\,\ f(x)=x^2\!-1\,\Rightarrow\,f(3)\equiv 0\equiv f(1)\ \ but\ \ x^2\!-1\not\equiv (x\!-\!3)(x\!-\!1)\equiv x^2\!-4x+3$$