Polynomial Long Division

Definition 1. A function $f : \mathbb R \to \mathbb R$ is called a polynomial if there exists real numbers $a_0,a_1,\dots, a_n$ with $a_n \geq 0$ such that

$\displaystyle f(x) = a_0 + a_1x + \cdots + a_nx^n \equiv \sum_{k=0}^n a_k x^k.$

In this context, we define $0^0 := 1$ for convenience. We leave it as an exercise that given polynomials $f,g$ , the functions $f + g$ and $f \cdot g$ are polynomials too. Define the degree of a polynomial by $\deg(0) := -\infty$ and $\deg(f) := n$ .

Remark 1. All needful real-analytic definitions have been rigorously established in undergraduate real analysis.

Problem 1. For any polynomial $f$ and real number $c$ , prove that there exists a unique polynomial $\tilde f$ such that $f(x) - f(c) = (x-c) \cdot \tilde f(x)$ .

(Click for Solution)

Solution. Suppose $c = 0$ for simplicity. Write $f$ as

$\displaystyle f(x) = \sum_{i=0}^n a_i x^i\quad \Rightarrow \quad f(0) = a_0.$

Therefore,

$\displaystyle f(x) - f(0) = \sum_{i=1}^n a_i x^i = x \cdot \underbrace{ \sum_{j=0}^{n-1} a_{j+1} x^j }_{\tilde f(x)} = x \cdot \tilde f(x).$

Now assume general $c$ . Define $g := f(c + \cdot)$ , which can be shown to be a polynomial with $\deg(f) = \deg(g)$ , since the binomial theorem yields

$\begin{aligned} g(y) = f(c+y) &= \sum_{i=0}^n a_i (c+y)^i \\ &= \sum_{i=0}^n a_i \sum_{j=0}^i {i \choose j} c^{j-i} y^j \\ &= \sum_{i=0}^n \sum_{j=0}^i a_i {i \choose j} c^{j-i} y^j \\ &= \sum_{j=0}^n \underbrace{ \sum_{i=j}^n a_i {i \choose j} c^{j-i} }_{b_j} y^j = \sum_{j=0}^n b_j y^j ,\end{aligned}$

and $b_n = a_n \neq 0$ . Use the previous result to obtain a polynomial $\tilde g$ such that $g(y) = y \cdot \tilde g(y)$ so that

$\displaystyle f(x) = g(c+(x-c)) = (x-c) \cdot \tilde g(x-c) =: (x-c) \cdot \tilde f(x),$

where $\tilde f := \tilde g(-c + \cdot)$ is also a polynomial.

Problem 2. Given polynomials $f,g$ , prove that

$\begin{aligned} \deg(f +g) &\leq \max\{\deg(f), \deg(g)\}, \\ \deg(f \cdot g) &= \deg(f) + \deg(g). \end{aligned}$

(Click for Solution)

Solution. If $f = 0$ , then $\deg(f+g) = \deg(g)$ and $\deg(f \cdot g) = \deg(0) = -\infty$ trivially. Suppose $f,g$ are nonzero. Write

$\displaystyle f(x) = \sum_{i=0}^m a_i x^i,\quad g(x) = \sum_{j=0}^n b_j x^j.$

Define $\alpha := \min\{m,n\}$ and $\beta := \max\{m,n\}$ . If $m < n$ , define $a_i = 0$ for $\alpha < i \leq \beta$ . Define similarly in the case $n < m$ . Then

$\displaystyle f(x) = \sum_{i=0}^{\alpha} a_i x^i + \sum_{i=\alpha+1}^{\beta} a_i x^i,\quad g(x) = \sum_{j=0}^{\alpha} b_j x^j + \sum_{j=\alpha+1}^{\beta} b_j x^j.$

It follows that

$\displaystyle (f+g)(x) = f(x) +g(x) = \sum_{i=0}^{\alpha} (a_i + b_i) x^i + \sum_{i=\alpha+1}^{\beta} (a_i + b_i) x^i.$

Therefore, $\deg(f+g) \leq \beta = \max\{m,n\}$ . The result for the product holds similarly:

$\begin{aligned} (f \cdot g)(x) = f(x) \cdot g(x) &= \left( \sum_{i=0}^m a_i x^i \right) \cdot \left( \sum_{j=0}^n b_j x^j \right) \\ &= \sum_{i=0}^m \sum_{j=0}^n a_i b_j x^i x^j \\ &= \sum_{i=0}^m \sum_{k=i}^{n+i} a_i b_{k-i} x^{k} \\ &= \sum_{k=0}^{m+n} \underbrace{ \sum_{i=0}^k a_i b_{k-i} }_{c_k} x^{k} = \sum_{k=0}^{m+n} c_k x^{k}. \end{aligned}$

Furthermore, $c_{m+n} = a_m \cdot b_n \neq 0$ . Hence, $\deg(f \cdot g) = m+n$ .

Problem 3. Prove that for nonzero polynomials $f, g$ , there exists unique polynomials $q, r$ with $\deg(r) < \deg(f)$ such that

$\displaystyle g = q \cdot f + r.$

(Click for Solution)

Solution. We will first prove existence. Write

$\displaystyle f(x) = a_m x^m + \tilde f(x) ,\quad g(x) = b_nx^n + \tilde g(x),$

where $\deg(\tilde f) < m$ and $\deg(\tilde g) < n$ . If $m = n$ , then

$\displaystyle g = \underbrace{ \frac{b_n}{a_n} }_{q} \cdot f + \underbrace{ \tilde g - \frac{b_n}{a_n} \cdot \tilde f }_{r},$

where $\deg(r) \leq \max\{\tilde f, \tilde g\} < \deg(f)$ . If $m > n$ , then $g = 0 \cdot f + g$ , and we set $q := 0, r := g$ , since

$\deg(r) = \deg(g) = n < m = \deg(f)$

works. We will prove the case $m < n$ by strong induction on $n$ . If $n = 1$ , then $m = 0$ implies the constant function $f = a_0$ , so that

$\displaystyle g(x) = b_1 x + b_0 = a_0 \underbrace{\left(\frac{b_1}{a_0}\cdot x + \frac{b_0}{a_0}\right)}_{q(x)} = f(x) \cdot q(x) + r(x),$

where we define $r = 0$ . Then

$\deg(r) = \deg(0) = -\infty < 0 = \deg(f)$

works. Suppose the statement holds in the case $n \leq k$ , and now assume $n = k+1$ . Define $l := n-m>0$ . We observe that

$\displaystyle \underbrace{ \frac{b_n}{a_m} \cdot x^l }_{p(x)} \cdot f(x) = g(x) - \tilde g(x) + x^l \cdot \frac{b_n}{a_m} \cdot\tilde f(x).$

Hence, $\deg(g - p \cdot f) \leq \max\{\tilde f, \tilde g\} < \deg(g)$ . If $\deg(g - p \cdot f) \leq \deg(f)$ , then we can find polynomials $\tilde q, \tilde r$ with $\deg(\tilde r) < \deg(f)$ such that

$\displaystyle g - p \cdot f = \tilde q \cdot f + \tilde r\quad \Rightarrow \quad g = (p+\tilde q) \cdot f + \tilde r.$

Otherwise, suppose $\deg(f) < \deg(g - p \cdot f) \leq k$ . By the induction hypothesis, we can find polynomials $\tilde q, \tilde r$ with $\deg(\tilde r) < \deg(f)$ such that