Polynomial Interpolation by Remainder Factor Theorem

There are several ways that we can deduce the actual form of a polynomial. If we are given enough values at specific points, we can use Lagrange interpolation or method of differences to figure out the polynomial. However, if we were instead given various equations which hold, then the more natural way is to apply the remainder-factor theorem.

This wiki assumes familiarity with the remainder-factor theorem and the fundamental theorem of algebra.

Introductory application of remainder-factor theorem:

Consider a generalized $n^\text{th}$-degree polynomial:

$$f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_1 x + a_ 0 \; .$$

In order to determine all the $(n+1)$ coefficients, $a_0,a_1,a_2,\ldots,a_n$, we need to know at least $(n+1)$ points of $\big(x,f(x)\big)$. And it is most common that we determine these coefficients by solving a system of linear equations simultaneously. However, as $n$ becomes larger, it becomes more and more impractical to solve them by hand. So is there a better alternative? Yes, there is, and it involves direct application of the remainder-factor theorem. To illustrate this point, let us consider a polynomial in the following:

Consider a quadratic polynomial $f(x)$ that satisfies

$$f(1) = 1^3 ,\qquad f(2) = 2^3, \qquad f(3) = 3^3,$$

and we are interested to find the unknowns in the quadratic polynomial, $f(x) = ax^2+bx+c$. Recall that by the remainder theorem, we have remainder of ${ax^2+bx+c}$ upon division by $x-1,x-2, x-3$ to be $1^3,2^3,3^3$, respectively. This tells us we need to solve the following equations simultaneously:

$$\begin{aligned} a(1)^2 + b(1) + c &= & 1^3 \\ a(2)^2 + b(2) + c &= & 2^3 \\ a(3)^2 + b(3) + c &= & 3^3. \end{aligned}$$

However, solving them simultaneously can get cumbersome and/or tedious. So is there an alternative approach? Yes, there is! We could, in fact, avoid solving these equations simultaneously, and the way to do so is to apply the second part of the remainder-factor theorem: factor theorem.

Factor Theorem

Let $f(x)$ be a polynomial such that $f(c) =0$ for some constant $c$. Then $x-c$ is a factor of $f(x)$. Conversely, if $x-c$ is a factor of $f(x)$, then $f(c)=0$.

But how is it related to our polynomial? Well, If we consider a dummy polynomial $g(x)$ such that it has roots of 1, 2, and 3. Then, by the factor theorem, we have $g(x) = A(x-1)(x-2)(x-3)$ for some constant $A$. Similarly, we know that $f(k) = k^3$ for $k=1,2,3$. Thus, like $g(x)$, the equation $f(k) - k^3 = 0$ has roots of 1, 2, and 3 as well. Hence, we can find the relationship between $g(x)$ and $f(x)$ to get $g(x) = f(x) - x^3 = A(x-1)(x-2)(x-3)$. With that we know,

$$f(x) - x^3 = A(x-1)(x-2)(x-3) \Rightarrow f(x) = x^3 + A(x-1)(x-2)(x-3).$$

But since we know $f(x)$ is a quadratic polynomial, the coefficient of $x^3$ in $f(x)$ must be 0, so $A$ is forced to be $-1$. Then we have $f(x) = x^3 - (x-1)(x-2)(x-3) = 6 x^2-11 x+6$. So, we have successfully found the unknown values of $a,b$ and $c$ from the polynomial of $f(x)$, and we did not have to solve any equations below simultaneously, which would have otherwise wasted plenty of our time.

$$\begin{aligned} a(1)^2 + b(1) + c &= & 1^3 \\ a(2)^2 + b(2) + c &= & 2^3 \\ a(3)^2 + b(3) + c &= & 3^3. \end{aligned}$$

Let's try out another similar example that applies this very concept:

Let $f(x)$ denote a $4^\text{th}$-degree polynomial such that $f(1) = 1, f(2) = 1, f(3) = 1, f(4) = 1$. Is there sufficient information to find the numerical value $f(5)?$ Why or why not?

---

It might be tempting to say that because $f(k) = 1$ for $k=1,2,3,4$, it naturally follows that $f(5)= 1$, but this is not necessarily true because we cannot extrapolate these data to assume that the trend continues as well. In fact, we can show that $f(5) \ne 1$ by recalling the fundamental theorem of algebra, but that is a discussion for another day. Now, back to the question: how do we find $f(5)?$ To find $f(5)$, we need to find the exact formula for $f(x)$ first. Since it is given that $f(x)$ is a $4^\text{th}$-degree polynomial, we have $f(x) = ax^4 + bx^3 + cx^2 + dx + e$ for unknown constants $a,b,c,d,$ and $e$. And we need to find all these unknowns first! Quite a handful of steps, isn't it? Fear not! Let's apply what we learned earlier.

Consider a dummy polynomial $g(x)$ such that it has roots $1,2,3,4$, then

$$g(x)= A(x-1)(x-2)(x-3)(x-4) .$$

Similarly, knowing that $f(k) - 1 = 0$ has roots $1,2,3,4$ as well, $f(k)- k$. Hence, we can find the relationship between $g(x)$ and $f(x)$ to get $g(x) = f(x) - 1= A(x-1)(x-2)(x-3)(x-4)$, or equivalently,

$$f(x) = A(x-1)(x-2)(x-3)(x-4) + 1.$$

So $f(5) = A(5-1)(5-2)(5-3)(5-4) + 1 = 24A + 1$. But wait! Can't we push further? In fact, we can't push any further; this is because we only know 4 points for a degree-4 polynomial, when in fact we need to know at least $(n+1)$ points for an $n^\text{th}$-degree polynomial. $_\square$

We are given additional information regarding this polynomial:

As shown in the last example above, we know that to determine all the coefficients of an $n^\text{th}$-degree polynomial, we need to know at least $(n+1)$ points. But is it mandatory to know this extra point to determine all its coefficients? Not exactly, because we could have known other facts as well. For example, if we know that the additional information that $f(x)$ is monic, then from the equation $f(x) = A(x-1)(x-2)(x-3)(x-4) + 1$, the leading coefficient $A$ has to be equal to $1$ by the definition of a monic polynomial, and thus we can determine the value of $f(5)$ to be $24(1) + 1 = 25$. Below is some common additional information regarding a polynomial that it might not be that obvious what we should be doing in the first place.

(i) We are given the value of a leading coefficient (the leading coefficient is 1 if the polynomial is monic).
(ii) We are given the constant term of the polynomial.

A degree 5 polynomial $f(x)$

• leaves a remainder of 1 when divided by $x-1;$
• leaves a remainder of 2 when divided by $x-2;$
• leaves a remainder of 3 when divided by $x-3;$
• leaves a remainder of 4 when divided by $x-4;$
• leaves a remainder of 5 when divided by $x-5$.

What is $f(x)$ if $f(x)$ is monic? What is $f(x)$ if its constant term is 240 instead?

---

Observe that $f(x) - x$ is divisible by $x-1, x-2, x-3, x-4, x-5$. Since these linear factors are distinct, we have

$$f(x) - x = A ( x-1)(x-2)(x-3)(x-4)(x-5) .$$

We are given that $f(x)$ is a degree-5 monic polynomial, which tells us that $A = 1$. Then

$$f(x) = (x-1)(x-2)(x-3)(x-4)(x-5) + x. \ _\square$$

Now, if the constant term of $f(x)$ is 240 instead, then we know that $f(0) = 240$, which implies

$$\begin{aligned} f(0) - 0 &=& A(0-1)(0-2)(0-3)(0-4)(0-5) \\ 240 - 0 &=& -120A \\ A &=& -2. \end{aligned}$$

Therefore, in this case $f(x) = -2 (x-1)(x-2)(x-3)(x-4)(x-5) + x. \ _\square$

Are you confident to test out these newly acquired skills? Give it a try with the following problems:

• Applying to a subset of the values, where it's clear what the polynomial form is.
• Test against the other given values.
• Cases where the "odd one out" is in the sequence, like when $f(1) = 0, f(2) = 1, f(3) = 4, f(5) = 8$.

Suppose we are given conditions for a function to have a pattern for some numbers that is not a polynomial. Then it isn't as easy; for example, if a $3^\text{rd}$-degree monic polynomial $f(x)=\frac{1}{x}$ for $x=1,2,3,$ then we can't have

$$f(x)=(x-1)(x-2)(x-3)+\dfrac{1}{x}$$

because then we won't have it as a polynomial. So what do we do then? Let's see the following examples:

Let a monic $3^\text{rd}$-degree polynomial satisfy

$$f(n)=\dfrac{1}{n},~~ n=1,2,3.$$

Find $f(n).$

---

First, if $f(n)$ is a monic cubic polynomial, then $nf(n)$ is a monic quartic polynomial. We see that

$$nf(n)=1,\ n=1,2,3\implies nf(n)=(n-1)(n-2)(n-3)(n+a)+1,$$

where the factor of $n+a$ was added to make it a quartic. How do we find $a?$ Note that $n$ must divide the RHS for $f(n)$ to be a polynomial, so by the remainder-factor theorem

$$(0-1)(0-2)(0-3)(0+a)+1=0\implies a=\dfrac{1}{6}.$$

Therefore, we finally have

$$f(n)=\dfrac{(n-1)(n-2)(n-3)\left(n+\frac{1}{6}\right)+1}{n}. \ _\square$$

Let's see another example of this kind.

$g(x)$ is a monic quadratic polynomial such that

$$g(x)=\dfrac{1}{x^2}, ~~x=1,2.$$

Find $g(x).$

---

Since $x^2g(x)$ is a monic quartic polynomial, we have

$$\begin{aligned} x^2g(x)&=(x-1)(x-2)(x+a)(x+b)+1\\ (0-1)(0-2)(0+a)(0+b)+1&=2ab+1\\&=0\\ \Rightarrow b&=\dfrac{-1}{2a}. \end{aligned}$$

We substitute this back in to get

$$\begin{aligned} x^2g(x) &=(x-1)(x-2)(x+a)\left(x-\frac{1}{2a}\right)+1\\ &=\big(x^2-3x+2\big)\left(x^2+\Big(a-\dfrac{1}{2a}\Big)x-\dfrac{1}{2}\right)+1. \end{aligned}$$

We don't need to expand the whole thing as we just need the coefficient of $x$ to be 0 $($for $x^2$ to divide$):$

$$2a-\dfrac{1}{a}+\dfrac{3}{2}=0\implies a-\dfrac{1}{2a}=\dfrac{-3}{4}.$$

So we have

$$g(x)=\dfrac{\big(x^2-3x+2\big)\left(x^2-\dfrac{3}{4}x-\dfrac{1}{2}\right)+1}{x^2}. \ _\square$$

A monic $10^\text{th}$-degree polynomial satisfies

$$f(x)=\binom{x}{6}, ~~x=0,1,2,....,9.$$

Find $f(x).$

---

We remember that $\binom{x}{6}=\frac{x(x-1)(x-2)(x-3)(x-4)(x-5)}{6!}$. So it is a polynomial. We can easily find $f$ to be

$$f(x)=x(x-1)(x-2)(x-3)\cdots (x-9)+\binom{x}{6}. \ _\square$$

Let

$$f(x)=2^x, ~~x=0,1,2,3,4,5,$$

where $f$ is a monic $6^\text{th}$-degree polynomial. Find $f(x).$

---

We recall 2 things: $2^x=\sum_{n=0}^x \binom{x}{n}~\forall x\in \mathbb{N}$ and $\binom{x}{n}$ is a polynomial and is zero if $x<n.$ So We can write

$$f(x)=2^x=\sum_{n=0}^5 \dbinom{x}{n}, ~~x=0,1,2,3,4,5.$$

We find that $\text{deg}\left(\sum_{n=0}^5 \binom{x}{n}\right)=5.$ Thus, since the degree is $>5,$ we can use RFT to get

$$f(x)=x(x-1)(x-2)(x-3)(x-4)(x-5)+\sum_{n=0}^5 \dbinom{x}{n}. \ _\square$$

We know how to solve systems of equations systematically by substitution and elimination. When the equations exhibit a clear pattern, however, we can write them in terms of polynomials, thus converting the system into a polynomial problem.

Here is a conversion problem:

$$\begin{aligned} a+3b+9c&=1 \\ a+4b+16c&=2 \\ a+5b+25c&=3 \end{aligned}$$

Notice the pattern here is that the coefficient of $c$ is the square of the coefficient of $b$, while the coefficient of $a$ stays constant. We can summarize this observation with a quadratic as follows:

$$f(x)=a+bx+cx^2 ~~\text {such that}~~ f(3)=1, ~f(4)=2, ~f(5)=3.$$

When is this conversion useful? If the problem asks to find the value of expressions like $a+b+c$ or $a+6b+36c$, then it suffices to find $f(1)$ and $f(6)$, which can be quickly done using the method of difference. Imagine having to solve for $a,b,c$ first and then plugging them in to find the answer! This method becomes more appealing when the number of variables is large. A long list of equations turns into points $\big(x,f(x)\big).$

Here is another conversion problem:

$$\begin{aligned} a+4b+9c&=1 \\ 4a+9b+16c&=2 \\ 9a+16b+25c&=3 \end{aligned}$$

Notice that the coefficients here are consecutive squares:

$$f(x)=ax^2+b(x+1)^2+c(x+2)^2 ~~\text {such that}~~ f(1)=1, ~f(2)=2, ~f(3)=3.$$

By now you'll get the idea. When in doubt, try to model one of the equations using polynomials and see if the other equations follow suit. In fact, constructing polynomials is not limited to just linear equations. Be creative!