# The Unapologetic Mathematician

## Polynomial Division

Polynomials generally form a ring, and not a field. However, the integers also form a ring, and we have a notion of division from arithmetic. For polynomials we have a similar form of division we’ll discuss now. Instead of using the absolute value of an integer to measure its size, we’ll use the degree of a polynomial to measure its size.

Given two polynomials $a$ and $b\neq0$, we can find two more polynomials — the quotient $q$ and the remainder $r$ — so that $a=qb+r$, and $\deg(r)<\deg(b)$. These polynomials are unique. The fact that we can find them is called the “division algorithm”, even though it’s a theorem. There are various algorithms we can use to establish this fact, but one of the most straightforward is polynomial long division, which we were all taught in high school algebra.

We start by writing $\displaystyle a=0b+a$. If the degree of $a$ is less than that of $b$, we’re done. Otherwise let’s write $\deg(a)=n$ and $\deg(b)=m$. The polynomials lead off with terms $a_nX^n$ and $b_mX^m$. If we multiply $b$ by $\frac{a_n}{b_m}X^{n-m}$ its leading term becomes exactly the same as that of $a$, so when we subtract the top degree terms cancel out. That is, we write $a=\frac{a_n}{b_m}X^{n-m}b+c$, and we see that $c$ has degree less than that of $a$.

Now if the degree of $c$ is still greater than or equal to that of $b$ we can keep going. Multiply $b$ by a term so that when we subtract the product from $c$ we’ll kill off the highest remaining term and drop its degree. Since the degree of the remainder keeps going down, it must eventually drop below that of $b$. Even if the degree of $b$ is zero, we can get the remainder down to the polynomial ${0}$, which we decided to give the degree $-\infty$. This gives us our $q$ and $r$

Now for uniqueness. Let’s say we have $a=q_1b+r_1$ and $a=q_2b+r_2$, and both $r_1$ and $r_2$ have degrees less than that of $b$. We can subtract to find $(q_1-q_2)b=(r_2-r_1)$. Now the degree on the right must be less than that of $b$, since adding and subtracting polynomials can’t increase the degree beyond the larger of the two. On the left, on the other hand, the degree is at least that of $b$, with one exception: if $q_1-q_2=0$. In this case the left hand side vanishes. Since this is the only way to drop the degree of the left-hand side we must have $q_1=q_2$. And then on the right we find $r_1=r_2$.

August 4, 2008 - Posted by | Algebra, Polynomials, Ring theory

1. […] Algorithm for Polynomials Consider the division algorithm. It looks a lot like division for integers, as it should. Specifically, it’s got all the […]

Pingback by Euclid’s Algorithm for Polynomials « The Unapologetic Mathematician | August 5, 2008 | Reply

2. […] we know from the fact that is a root that is a factor of . Our division algorithm shows us that we can write . The factor that gives us the root shows up twice! But since […]

Pingback by Polynomials with Too Few Roots « The Unapologetic Mathematician | August 6, 2008 | Reply