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.

About these ads

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

2 Comments »

  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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 388 other followers

%d bloggers like this: