The Unapologetic Mathematician

Mathematics for the interested outsider

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 | 2 Comments