Proof that a polynomial over a field has at most as many roots as its degree

Proof

Let $K$ be a field. For a nonzero $h \in K[x]$, let $Z(h)$ be the set of roots of $h$ in $K$. For $d \in K$, let $m_h(d)$ be the multiplicity of $d$ as a root of $h$. We prove by induction on $n \ge 0$ this claim: every nonzero $f \in K[x]$ of degree $n$ has $Z(f)$ finite and $\sum_{d \in Z(f)} m_f(d) \le n$.

1. The field $K$ is an integral domain: $1 \ne 0$, and if $a b = 0$ with $a \neq 0$, then $b = a^{-1} a b = 0$.
2. So $K[x]$ is an integral domain by the theorem on polynomial rings, and $\deg(g h) = \deg g + \deg h$ by the degree of a product. Nonzero factors cancel in $K$ and in $K[x]$.
3. Let $h \neq 0$ and $d \in Z(h)$. By the factor theorem, $x - d$ divides $h$, so $m_h(d) \ge 1$. Conversely, if $m_h(d) \ge 1$, then $x - d$ divides $h$ and $d \in Z(h)$.
4. By step 3, the claim gives $\abs{Z(f)} \le \sum_{d \in Z(f)} m_f(d) \le n$. So the claim implies both parts of the statement.
5. Let $f \neq 0$ have degree $n$. If $f$ has no root, then $Z(f)$ is empty and the sum is $0 \le n$. This covers $n = 0$: a nonzero constant $a$ has the value $a \neq 0$ everywhere.
6. Now let $n \ge 1$, assume the claim for degree $n - 1$, and let $c$ be a root of $f$. By the factor theorem, $f = (x - c) g$ with $g \in K[x]$.
7. Since $f \neq 0$, also $g \neq 0$. By step 2, $n = 1 + \deg g$, so $\deg g = n - 1$.
8. For $d \in K$, the evaluation homomorphism gives $f(d) = (d - c) g(d)$. By step 1, $f(d) = 0$ exactly when $d = c$ or $g(d) = 0$. So $Z(f) = Z(g) \cup \set{c}$.
9. By the induction hypothesis, $Z(g)$ is finite, so $Z(f)$ is finite.
10. Let $d \neq c$. We show by induction on $m \ge 0$ that for every $g_0 \in K[x]$, if $(x - d)^m$ divides $(x - c) g_0$, then $(x - d)^m$ divides $g_0$. The case $m = 0$ is trivial.
11. Let $m \ge 1$ and $(x - c) g_0 = (x - d)^m k$ with $k \in K[x]$. Evaluating at $d$ gives $(d - c) g_0(d) = 0$. Since $d - c \neq 0$, step 1 gives $g_0(d) = 0$.
12. By the factor theorem, $g_0 = (x - d) g_1$ with $g_1 \in K[x]$. Then $(x - d)(x - c) g_1 = (x - d)(x - d)^{m-1} k$.
13. Cancelling the nonzero factor $x - d$ gives $(x - c) g_1 = (x - d)^{m-1} k$. By the induction hypothesis of step 10, $(x - d)^{m-1}$ divides $g_1$, so $(x - d)^m$ divides $g_0$.
14. If $(x - d)^m$ divides $g$, then it divides $f = (x - c) g$. With step 10 for $g_0 = g$, this gives $m_f(d) = m_g(d)$ for each $d \neq c$.
15. Let $m \ge 1$. If $(x - c)^m k = (x - c) g$, then cancelling $x - c$ gives $g = (x - c)^{m-1} k$. Conversely, $g = (x - c)^{m-1} k$ gives $f = (x - c)^m k$.
16. So $(x - c)^m$ divides $f$ exactly when $(x - c)^{m-1}$ divides $g$, for each $m \ge 1$. Taking the largest such $m$ gives $m_f(c) = 1 + m_g(c)$.
17. If $c \notin Z(g)$, then $m_g(c) = 0$ by step 3. So in all cases $m_g(c) + \sum_{d \in Z(g), d \neq c} m_g(d) = \sum_{d \in Z(g)} m_g(d)$.
18. By steps 8, 14, 16 and 17, $\sum_{d \in Z(f)} m_f(d) = 1 + m_g(c) + \sum_{d \in Z(g), d \neq c} m_g(d) = 1 + \sum_{d \in Z(g)} m_g(d)$.
19. By the induction hypothesis for $g$, this is at most $1 + (n - 1) = n$. This proves the claim, and with step 4 the statement.