Proofs involving the Remainder theorem

March 24, 2010

The Remainder theorem, sometimes called the Little Bezout theorem states the following:

If P(x) is a polynomial function, then the remainder of P(x) when divided by x-k is equal to P(k).

Example

Say we wanted to find the remainder of P(x) = x^3 - 2x^2 - 6x - 7 divided by x-4. We evaluate P(4) which gives 1.

The other way to find the remainder would be by polynomial long division:

Hosted by imgur.com

This calculation is somewhat wasted if we only want to calculate the remainder, as it takes considerably more work than evaluating a polynomial.

Notice however that if the goal was to obtain the remainder, Synthetic division would be the better method.

To calculate the remainder of a n^{th} degree polynomial requires n multiplications and n-1 additions, for both the remainder theorem and synthetic division.

In addition, division gives both the quotient and the remainder while evaluating the polynomial gives only the remainder.

Proof of the Remainder Theorem

Consider that a polynomial P(x) after division results in D(x) \cdot Q(x) + R where D is the divisor, Q is the quotient, and R is the remainder.

In this case, the polynomial is divided by x-k where k is a constant. This is the divisor, so D(x) = x-k.

Substituting the divisor into the polynomial, we have:

\begin{array}{l} P(x) = D(x) \cdot Q(x) + R \\ P(x) = (x-k) \cdot Q(x) + R \end{array}

From here, you can easily see that P(k) = R:

\begin{array}{l}P(k) = (k-k) \cdot Q(x) + R \\ P(k) = R \end{array}

Q.E.D. (not sure if this is correct usage or not)

Why x^n – y^n is divisible by x-y

Hosted by imgur.com

No idea why my writing tends to slide downwards to the right. I don’t have this problem on paper, only when drawing stuff with the mouse on MS-paint.

Anyways, we start with the polynomial P(x) = x^n - y^n. The variable y is still a variable, but takes the position of k in the remainder theorem.

Evaluating P(y), we get 0. Therefore the remainder of P(x) when divided by x-y is zero, meaning x-y is a factor of P(x).

Why x^n + y^n is sometimes but not always divisible by x+y

Hosted by imgur.com

Again with the similar polynomial P(x) = x^n + y^n, we have x-k as a factor if P(k)=0.

The expression x+y is divisible only when P(-y) = 0. In other words:

\begin{array}{l} (-y)^n + y^n = 0 \\ (-y)^n = -y^n \end{array}

If n is even:

(-y)^n = y^n

However if n is odd:

(-y)^n = -y^n

Therefore, it’s only when n is odd that x^n + y^n is divisible by x+y.


Notes on interpolating polynomials

February 12, 2010

My first post here, so I’m not really sure how to do all the formatting and stuff. It’ll take me a while to get used to the Latex.

I’ll get started.

We have a set of points, [(x_0,y_0), (x_1,y_1), \cdots, (x_n,y_n)] ; how would we find a polynomial function f(x) that passes through all of the points?

Let’s have an example here. We have the four points (1,100), (2,30), (3,70), (4,1000) and we need to find a polynomial function so that f(1) = 100, f(2) = 30, f(3) = 70, and f(4) = 1000.

Remember that a polynomial function of order n can be represented by f(x) = a_0 x^n + a_1 x^{n-1} \cdots a_{n-1} x + a_n. So a line would be f(x) = a_0 x + a_1 , which is more commonly seen as y = mx + b. Similarly a quadratic would be f(x) = a_0 x^2 + a_1 x + a_2.

What we need to do to find the polynomial is to determine a set of coefficients a_0, a_1, \cdots, a_n so that for every point (x,y) in our set of points [(x_0,y_0),(x_1,y_1),\cdots,(x_n,y_n)] the statement y = a_0 x^n + a_1 x^{n-1} + \cdots + a_n is true.

Notice here that the number of coefficients a_n is always one more than the order of the function. This implies that to interpolate a polynomial of P points we need an order P-1 polynomial.

We have four points, so we need to determine the correct cubic polynomial:

y = ax^3 + bx^2 + cx + d

We simply substitute the four points into the equation:

100 = a (1)^3 + b (1)^2 + c (1) + d
30 = a (2)^3 + b (2)^2 + c (2) + d
70 = a (3)^3 + b (3)^2 + c (3) + d
1000 = a (3)^3 + b (3)^2 + c (3) + d

Simplify:

a + b + c + d = 100
8a + 4b + 2c + d = 30
27a + 9b + 3c + d = 70
64a + 16b + 4c + d = 1000

Now we have a simple set of linear equations. We solve this and get:

a = 130
b = -725
c = 1195
d = -500

y = 130 x^3 - 725 x^2 + 1195 x - 500

Plot this in Mathematica:

Of course we could have saved all that work and just used the built in function:

Expand[InterpolatingPolynomial[{{1, 100}, {2, 30}, {3, 70}, {4,
    1000}}, x]]

> -500 + 1195 x - 725 x^2 + 130 x^3

So now that we know how to do polynomial interpolation, let’s have some fun with this. Take the Runescape level XP table (don’t laugh) and find a function that generates these values.

I used Vim to transform the table into a mathematica input, then computed the 98-th degree generating polynomial. The computation only took about a second, and produced a very large (several pages worth) output. Here’s an image.

This is normal, right? Now let’s try plotting the polynomial, as before:

Yes, this function passes through all of our 99 points. But with such a large number of points, the function oscillates wildly between points. This is known as Runge’s phenomenon.


Follow

Get every new post delivered to your Inbox.

Join 69 other followers