# 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. – please delete me 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.

-

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 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 20 hours ago

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 $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 at 11:30
It is so on purpose. I would simply want to point OP in a direction. – M. Fischer Jun 15 at 13:21