# 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$? (Except $n=0$ where $f(x)$ is $0$ in all cases)

• Induction. If it has a root r, divide by (x - r). – Qiaochu Yuan 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. – Eivind 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$ – kahen 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? – Aryabhata 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. – Aryabhata 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. – Pranav Bisht 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... – Aryabhata 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. – Noldorin 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? – FUZxxl 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
• @Doug This comment is confusing, Z/12Z is not a field as 12 is not prime, so what are you saying? – john Sep 25 '16 at 16:25
• 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

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.

There's probably a simple proof based on the fact that every polynomial of degree n has at most (n - 1) turning points. Clearly and without rigorous proof this points directly to the more general quality of a polynomial of degree n : it can only take on at most n identical values. And since the roots are a specific case when the value is 0, there clearly can be at most n roots.

Suppose that the polynomial is defined in the field $\mathbb C$[X] as:
$$f=\sum_{i=0}^na_iX^i$$ 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.

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)?$ – FUZxxl 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

Let $f$ be a polynomial, such that $f(r) = 0$. Define $f'(x) = \frac{f(x)}{x - r}$. Repeat this process, and consider the degree, $\deg(f^{(n)})$.

• Your argument is incomplete. – FUZxxl Jun 15 '16 at 11:30
• It is so on purpose. I would simply want to point OP in a direction. – user347499 Jun 15 '16 at 13:21