Division Algorithm for Polynomials

Prove this: Let f(x), g(x) be two polynomials with deg(f) ≤ deg(g). Then there are unique polynomials q(x), r(x) such that g(x) = q(x)f(x) + r(x), where deg(r) < deg(f).

Proof (Division Algorithm for Polynomials)

Let $f(x)$ and $g(x)$ be polynomials over a field (or integral domain) $K$, with

$$ \deg(f) \le \deg(g). $$

We will show:

1. Existence: there exist polynomials $q(x)$ and $r(x)$ such that

   $$ g(x) = q(x)\,f(x) + r(x), $$

   with $\deg(r)<\deg(f)$.

2. Uniqueness: this representation is unique.

---

1. Existence

We proceed by induction on $n = \deg(g)$.

• Base case: If $\deg(g) < \deg(f)$, then we may simply take

  $$ q(x) = 0, \qquad r(x) = g(x). $$

  Clearly $g = 0\cdot f + g$, and $\deg(r)=\deg(g)<\deg(f)$.

• Inductive step: Suppose the statement holds for all polynomials of degree less than $n$, and let $\deg(g)=n\ge\deg(f)$. Write

  $$ f(x) = a_m x^m + \dots,\quad g(x)=b_n x^n + \dots $$

  with $a_m,b_n\neq0$. Since $n\ge m$, set

  $$ t(x) \;=\;\frac{b_n}{a_m}\,x^{n-m}. $$

  Then $\deg\bigl(t(x)\,f(x)\bigr)=n$, and its leading coefficient matches that of $g(x)$. Consider

  $$ g_1(x) \;=\; g(x)\;-\;t(x)\,f(x). $$

  By construction, $\deg(g_1)<n$. Now by the induction hypothesis applied to $g_1$ (whose degree is $<n$), there exist polynomials $q_1(x)$ and $r(x)$ with

  $$ g_1(x) = q_1(x)\,f(x) + r(x), \qquad \deg(r)<\deg(f). $$

  Hence

  $$ g(x) = t(x)\,f(x) + g_1(x) = t(x)\,f(x) + \bigl(q_1(x)\,f(x) + r(x)\bigr) = \bigl(t(x)+q_1(x)\bigr)\,f(x) + r(x). $$

  Setting $q(x)=t(x)+q_1(x)$ gives the desired representation for $g$, with $\deg(r)<\deg(f)$.

By induction, such $q(x)$ and $r(x)$ always exist.

---

2. Uniqueness

Suppose there are two representations

$$ g(x) = q_1(x)\,f(x) + r_1(x), \qquad g(x) = q_2(x)\,f(x) + r_2(x), $$

with $\deg(r_1),\deg(r_2)<\deg(f)$. Subtracting gives

$$ 0 = \bigl(q_1(x)-q_2(x)\bigr)\,f(x)\;+\;\bigl(r_1(x)-r_2(x)\bigr). $$

Rearrange:

$$ \bigl(q_1(x)-q_2(x)\bigr)\,f(x) = -\bigl(r_1(x)-r_2(x)\bigr). $$

• The left side is a multiple of $f(x)$, so if $q_1\neq q_2$ then $\deg\bigl((q_1-q_2)f\bigr)\ge \deg(f)$.
• The right side is $r_2(x)-r_1(x)$, whose degree is strictly less than $\deg(f)$.

The only way a nonzero polynomial of degree $\ge\deg(f)$ can equal one of degree $<\deg(f)$ is if both are the zero polynomial. Hence

$$ q_1(x)-q_2(x) \;=\; 0, \quad r_1(x)-r_2(x)\;=\;0, $$

so $q_1 = q_2$ and $r_1 = r_2$. This proves uniqueness.

---

Together, these two parts establish the Division Algorithm for polynomials: for any $f(x)$ and $g(x)$ with $\deg(f)\le\deg(g)$, there exist unique polynomials $q(x)$ and $r(x)$ such that

$$ g(x) = q(x)\,f(x) + r(x), \quad \deg(r)<\deg(f). $$

$\quad\blacksquare$