# How to prove that a polynomial of degree $n$ has at most $n$ roots?

How can I prove, that a polynomial function $$f(x) = \sum_{0\le k \le n}a_k x^k\qquad n\in\mathbb N,\ a_k\in\mathbb C$$ is zero for at most $$n$$ different values of $$x$$, unless all $$a_0,a_1,\ldots,a_n$$ are zero?

• Induction. If it has a root r, divide by (x - r). Mar 8 '11 at 19:56
• Isn't this the fundamental theorem of algebra? Wikipedia (en.wikipedia.org/wiki/Fundamental_theorem_of_algebra) gives several proofs. Mar 8 '11 at 19:56
• Hint: First show that $f(\alpha) = 0$ iff $x-\alpha$ divides $f(x)$ and then use induction on the degree of $f$ Mar 8 '11 at 19:57
• Is there any background one needs to consider? For instance, is this some problem assigned in some course? If so, which course? Mar 8 '11 at 20:01
• @Fuz: No, it is not "part" of fundamental theorem. It might be what you call a "Corollary", but it has other easier proofs. Mar 8 '11 at 20:13

Using Linear Algebra,

If the $n+1$ distinct roots are $\alpha_i$, then we have that $x = [a_0, a_1, \dots, a_n]^{T}$ is a solution of $Ax = 0$ where $A$ is the Vandermonde matrix using the $\alpha_i$.

Since the Vandermonde matrix is invertible for distinct $\alpha_i$, it follows that $x = [0, 0, \dots, 0]$.

Thus if $a_j \neq 0$ for some $j$, then your polynomial can have at most $n$ different roots.

Note: This is basically saying that given a field $K$, any polynomial of degree $n$ in $K[x]$ has at most $n$ distinct roots.

Fundamental Theorem of Algebra is an assertion of the fact that $\mathbb{C}$ is algebraically closed, and the $K$ above need not be algebraically closed.

• I just hope that Vandermonde determinant formula in itself does not use the theorem asked in question. Apr 4 '17 at 17:09
• @PranavBisht: No. There is an explicit formula for the determinant of the Vandermonde matrix. It would actually be an interesting proof that uses the theorem in question to prove that the Vandermonde matrix is invertible... Apr 4 '17 at 20:34

You don't need the fundamental theorem of algebra or the Vandermonde determinant, only the factor theorem.

Proposition: A polynomial of degree at most n with more than n roots vanishes identically.

Proof: By induction. The base case is $n=0$, which is obvious. Now take a polynomial f of degree at most n, and let $x_1,\ldots,x_{n+1}$ be distinct roots of f. By the factor theorem, we can write $$f(x) = (x-x_{n+1})g(x)$$ where g plainly has degree at most $n-1$. Now substitute $x = x_i$ for $i=1,\ldots,n$. For all these values of x the left hand side vanishes and the factor $(x_i-x_{n+1})$ is nonzero. Hence all these $x_i$ must be roots of g and by induction g is identically zero. QED

This same proof works over any field (or even integral domain).

• for polynomials $f,g\in K[x]$ there are $q,r\in K[x]$ such that $f=qg+r$ with $\text{deg}(r)<\text{deg}(g)$ or $r=0$ (polynomial division). if $f(\alpha)=0$, take $g(x)=x-\alpha$ to get $0=f(\alpha)=r$. Hence $r=0$ and $f(x)=q(x)(x-\alpha)$.
– yoyo
Mar 8 '11 at 21:18

The following literature may be of use here:

Theorem. A polynomial $\text{f}$ of degree $\text{n}$ over a field $\text{F}$ has at most $\text{n}$ roots in $\text{F}$.*

Proof. The results is obviously true for polynomials of degree $0$ and degree $1$. We assume it to be true for polynomials of degree $n-1$. If $a$ is a root of $f$, $f=(x-a)q$ where $q$ has degree $n-1$. Since $f(b)=0$ if and only if $a=b$ or $q(b)=0$, it follows by our inductive assumption that $f$ has at most $n$ roots. $\Box$

• Most elegant proof of the lot. Apr 30 '14 at 17:25
• It's obvious that $f=(x-a)q$ if $a$ is a root, but how can that be demonstrated? Feb 26 '16 at 16:57
• Note that this proof uses the fact $F[x]$ is a UFD, so that the factorization $f(x) = (x-a)q(x)$ is unique. Without uniqueness the argument can fail. For instance, in $\mathbf{Z}/12\mathbf{Z}$ the polynomial $x^2 - 4$ has four roots $2, 4, 8, 10$ and two distinct factorizations $x^2 - 4 = (x - 8)(x - 4) = (x - 10)(x - 2)$. Note that the theorem holds if the field $F$ is replaced by any integral domain $R$ (see Dan Petersen's proof on this page). But I believe $R[x]$ need not be a UFD if $R$ is not a UFD.
– Doug
Jul 27 '16 at 0:32
• Hi john, the point I was making is that the proof by Trancot directly uses the fact $F$ is a field, where $F[x]$ then becomes a UFD. The result is false generally for rings that are not integral domains, e.g. $Z_{12}$. In this example, the proof by Trancot fails because $Z_{12}[x]$ is not a UFD.
– Doug
Sep 29 '16 at 19:43
• @Doug: No, this proof does not use that $F\left[x\right]$ is a UFD. All roots of $f$ other than $a$ are roots of $q$ (as the proof points out), so induction yields that there are at most $n-1$ of them. We don't need to consider two different factorizations $f = \left(x-a\right) q = \left(x-b\right) r$ of $f$; after factoring out $x-a$ from $f$, we then factor out the next $x-b$ from $q$ (not from $f$). Oct 25 '19 at 19:51

Just a clarification here. The Fundamental Theorem of Algebra says that a polynomial of degree n will have exactly n roots (counting multiplicity). This is not the same as saying it has at most n roots. To get from "at most" to "exactly" you need a way to show that a polynomial of degree n has at least one root. Then you can proceed by induction.

There are lots of different kinds of proofs that a polynomial must have at least one root. None of them are totally trivial.

Let $\alpha_1,\ldots,\alpha_{n+1}$ be distinct roots for $f(x)$ with ${\sf deg}(f)\leq n$. W.l.o.g, we can assume the leading coefficient of $f(x)$ is always $1$. This can be done by enumerating all the cases:

If ${\sf deg}(f)=n$, then $\alpha_1,\ldots,\alpha_n$ are roots implies $f(x)=(x-\alpha_1)\cdots(x-\alpha_n)$. But $f(\alpha_{n+1})\neq0$, so this does not work.

If ${\sf deg}(f)=n-1$, then $\alpha_1,\ldots,\alpha_{n-1}$ are roots implies $f(x)=(x-\alpha_1)\cdots(x-\alpha_{n-1})$. But $f(\alpha_n)\neq0$, so this does not work either.

$\vdots$

If ${\sf deg}(f)=1$, then $\alpha_1$ is a root implies $f(x)=x-\alpha_1$. But $f(\alpha_2)\neq0$, so this does not work either.

Hence this only case that would work is ${\sf deg}(f)=0$, and so $f(x)=0$.

• How do you prove that $f(x)=(x-\alpha_1)\cdots(x-\alpha_n)?$ Nov 28 '16 at 15:55
• @FUZxxl This is a consequence of factor theorem: $\alpha$ is a root of $f(x)$ iff $f(x)=(x-\alpha)g(x)$ where ${\sf deg}(g)={\sf deg}(f)-1$. And note that $\alpha_2$ is a root of $(x-\alpha_1)g(x)$ implies $\alpha_2$ is a root of $g(x)$...
– Easy
Nov 29 '16 at 1:58

Suppose that the polynomial is $$f=\sum_{i=0}^na_iX^i \in \mathbb{C}\left[X\right] .$$ Assume that the polynomial function defined by the above polynomial has $$n+1$$ distinct roots, i.e., $$f(x)=0$$ for $$n+1$$ distinct values of x $$\in \Bbb C$$.
I shall use the theorem:$$\prod_{i=1}^k\left(X-x_i\right)q=f \Longleftrightarrow x_1,...,x_k \text{ are distinct roots of }f\text{, where }q\in\Bbb C[X]$$ Let $$n+1$$ distinct roots of $$f$$ are $$x_1,...,x_{n+1}$$. Hence, by above theorem, we can say that $$\prod_{i=1}^{n+1}\left(X-x_i\right)q=f$$. Since the coefficient lie in the field of complex numbers, hence left hand side has degree $$n+1$$, while $$f$$ is of degree n. This is impossible, therefore $$f$$ can have at most n distinct roots.

Try Rolle's Theorem with induction.

For base case it works apparently.

Let set $$S = \{x : f(x)=0\}$$. For induction step, suppose that $$|S|\leq n$$ for $$f(t)$$ of degree $$n$$. Then we want to prove that $$|S|\leq n+1$$ for degree of $$n+1$$.

Suppose $$|S| > n+1$$ for degree of $$n+1$$, let $$x_1 < x_2 <... < x_{n+1} < x_{n+2}$$, where $$x_i \in S$$.

$$p(x_1)=...=p(x_{n+2})=0$$ By Rolle's Theorem we can find $$c_i \in (x_i, x_{i+1})$$ s.t. $$f'(c_i)=0 \forall i$$, where its derivative is just the case for degree $$n$$.

This implies that $$|S|>n$$ for the case of degree of $$n$$, which contradicts with our assumption.