Polynomial remainder theorem

From TCS Wiki
Revision as of 18:04, 4 May 2016 by imported>MishkaVodkaBalalaika (Created page with "The '''polynomial remainder theorem''' states that: for every polynomial <math>P(x)</math> and every real number <math>a</math> the remainder of division of <math...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

The polynomial remainder theorem states that:

for every polynomial [math]\displaystyle{ P(x) }[/math] and every real number [math]\displaystyle{ a }[/math] the remainder of division of [math]\displaystyle{ P(x) }[/math] by [math]\displaystyle{ x - a }[/math] is [math]\displaystyle{ P(a) }[/math].

This theorem can easily be proven, but it is important for various calculations.

Proof

If we divided [math]\displaystyle{ P(x) }[/math] by [math]\displaystyle{ x - a }[/math], it means that we found such [math]\displaystyle{ Q(x) }[/math] and [math]\displaystyle{ b }[/math], that

[math]\displaystyle{ P(x) = Q(x) \cdot (x - a) + b }[/math].

Let [math]\displaystyle{ x = a }[/math]. Then [math]\displaystyle{ P(a) = Q(a) \cdot (a - a) + b = 0 + b = b. }[/math] Q.E.D.

Example

Let's divide [math]\displaystyle{ P(x) = x^2 - 2x + 4 }[/math] by [math]\displaystyle{ x - 6 }[/math].

The theorem says that the remainder will be equal to [math]\displaystyle{ (6)^2 - 2 \cdot (6) + 4 = 36 - 12 + 4 = 28. }[/math]

So, let's divide [math]\displaystyle{ P(x) - 28 = x^2 - 2x - 24 }[/math] by [math]\displaystyle{ x - 6 }[/math]: [math]\displaystyle{ x^2 - 2x - 24 = (x - 6) (x + 4) }[/math].

We get that [math]\displaystyle{ x^2 - 2x + 4 = (x + 4) (x - 6) + 28 }[/math].

Uses

Sometimes, it can be difficult to calculate [math]\displaystyle{ P(a) }[/math] fast (if the polynomial is very big). There exist methods of fast division by [math]\displaystyle{ x - a }[/math], so the computing the remainder could be easier than the whole function.

The theorem itself is also very important for theoretical use. Its proof can easily be applied to another similar objects with little changes. It is used, for example, in the fundamental theorem of algebra, in the form of a generalisation in complex numbers.

Template:Math-stub