# Prove that a polynomial of degree $d$ has at most $d$ roots (without induction)

Let $p(x)$ be a non-zero polynomial in $F[x]$, $F$ a field, of degree $d$. Then $p(x)$ has at most $d$ distinct roots in $F$.

Is it possible to prove this without using induction on degree? If so, how can I do this?

-
Assume it has $d+1$ roots. Let $P(x)(x-x_1)(x-x_2) \cdots (x-x_{d+1})=0 \implies P(x)$ is of degree $d+1$. (Note that $x$ gets multiplied $d+1$ times). –  Inceptio May 27 '13 at 10:23
@Inceptio How do you show that the degree of the polynomial is $d+1$? You're using induction somewhere. ;-) –  egreg May 27 '13 at 10:24
@Inceptio aren't you using induction then? –  Ittay Weiss May 27 '13 at 10:24
@IttayWeiss: $x$ gets multiplied $d+1$ times is induction? –  Inceptio May 27 '13 at 10:26
I don't think this is possible without using directly or indirectly induction... –  DonAntonio May 27 '13 at 11:00

If $p(x)$ were to have more than $d$ distinct roots in $F$, then it would have at least $d+1$ linear factors $(x - r_1), (x - r_2), \cdots$. This is impossible.

-
and this uses induction.... –  Ittay Weiss May 27 '13 at 10:24
@IttayWeiss The OP desired a proof of this new statement not using induction on the degree of the polynomial. I doubt the OP wants to prove this without induction at all, i.e. s/he is OK with using facts which were proven before with induction. Indeed I would bet this result (and many much more fundamental results) are provably impossible without mathematical induction at all. –  6005 May 27 '13 at 10:32
It is presumably already shown that the product of any number of polynomials has degree equal to the sum. The OPs question is undoubtedly okay with this preproven result. –  6005 May 27 '13 at 10:33
this may very well be the case. Perhaps OP should clarify what is precisely allowed and what is not. –  Ittay Weiss May 27 '13 at 10:34
@Goos: I'm not really quite sure about how it is or it is not an induction.? –  Inceptio May 27 '13 at 10:39

I'm not sure if using the residue theorem counts, and this only works over $\Bbb C$, but :

Look at $\int P'(z)/P(z) \;dz$ where you integrate on a circle $|z| = r > |x_i|$.

As $r \to \infty$, this is equivalent to $\int d/z \;dz = 2id\pi$.
Meanwhile, the residue theorem says that the integral is $\sum 2i\pi \mu_i$ where $\mu_i$ is the multiplicity of the root $x_i$. Hence the number of roots, counted with their multiplicity, is equal to $d$, the degree of the polynomial.

-
I would +1, because this is a cute method. However, this proof fails over a general field $F$, and thus doesn't rigorously answer the OP's question. –  6005 May 27 '13 at 10:37

If $p(x)=0$ has a root $x=a$, then $p(a)=0$ and $p(x)=p(x)-p(a)$.

$p(x)-p(a)$ is the sum of terms like $c_rx^r-c_ra^r=c_r(x-a)(x^{r-1}+ax^{r-2}+a^2x^{r-3}+ \dots +a^{r-1})$

And since $x-a$ is a factor of every term, it is a factor of $p(x)$. So every root gives us a linear factor.

Suppose $p(x)=k(x-a_1)(x-a_2) \dots (x-a_d)$ of degree $d$ has the $d$ roots $a_1 \dots a_d$ and $b$ is distinct from all of these, then $p(b)$ is a product of non-zero factors, so cannot be equal to zero.

Is this a proof without induction? Difficult to say. For example, how do we prove that if $r$ divides each of $e_1, e_2 \dots e_n$ then it divides their sum?

But the division step, with $p(x)=(x-a)q(x)$ and $q(x)$ having strictly lower degree than $p(x)$ leads to a descending sequence of integers (the orders of the polynomials obtained by successive divisions) - and what we need to know for that is that (i) any strictly descending sequence of non-negative integers is finite; and (ii) we can bound the length of the sequence by $d$ - and we can do this by observing that there are $d$ non-negative integers less than $d$.

So it all depends on the properties of integers that we are allowed to assume - and that is because we need to say things about the degree of $p(x)$ - an integer, and we also need to do things like indexing the coefficients.

-