# Proofs involving the Remainder theorem

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:

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

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

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

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.