Associated Topics || Dr. Math Home || Search Dr. Math

```Date: 11/20/2005 at 19:12:26
From: Hans
Subject: Which is the polynomial factorization methodology

Hello Dr. Math!

I hope you can help me out.  I need to sort out all the methods that
one can use to get a polynomial factored.  Could you also provide
guidelines for factoring the polynomial x^5 + x + 1?

I tried to get that particular polynomial factored using Rational
Roots Test, Descarte's rule of signs, quadratic formula, common
factor, Newton's Method, and still no luck.

```

```
Date: 11/20/2005 at 20:21:44
From: Doctor Vogler
Subject: Re: Which is the polynomial factorization methodology

Hi Hans,

Thanks for writing to Dr. Math.  There are different ways to answer

(1) factor over the complex numbers
(2) factor over the real numbers
(3) factor over the rational numbers or the integers

In case (1), this is a matter of finding all five complex roots, since
every polynomial factors into a product of linear factors over the
complex numbers.

In case (2), the easiest way is to find the five complex roots and
then pair off the non-real complex factors and put them into quadratic
factors.  Every polynomial with real coefficients factors into a
product of linear factors and quadratic factors over the real numbers.
In both cases (1) and (2), you generally can't find the roots exactly,
so you use numeric methods (e.g. Newton's method) to get as accurate
values as you'd like.

Case (3) is more interesting, for the reason that it's more
challenging.  Polynomials might factor in many different ways over the
rational numbers.  You do have one theorem:  A polynomial with integer
coefficients that factors over the rationals will also factor over the
integers.  This means that factoring over rationals and factoring over
integers are really the same thing, at least if you start with a
polynomial with integer coefficients.

The easy way to factor a polynomial over the integers is to have a
math program do it for you.  For example, the very nice program GNU

http://pari.math.u-bordeaux.fr/

and you can just ask it for

factor(x^5+x+1)

You can also use more expensive math programs, like Mathematica, which
you can tell

Factor[x^5+x+1]

These programs use sophisticated factoring algorithms.  One such is

Berlekamp-Zassenhaus Algorithm
http://mathworld.wolfram.com/Berlekamp-ZassenhausAlgorithm.html

or here

Polynomial Factorization
http://math.berkeley.edu/~berlek/poly.html

or by searching Google for something like

berlekamp algorithm

or just

polynomial factorization

This kind of thing is more suited to computers and programming than it
is to pencil and paper, though.  If you have a small polynomial that
you want to factor by hand, then the easiest way is perhaps the naive
approach:

You consider how the polynomial might factor.  You only have to
consider two factors, because if it factors into more than two
factors, then it also factors into two factors.  A fifth-degree
polynomial that factors will have one of the following forms:

(degree 1) * (degree 4), or
(degree 2) * (degree 3).

The first form is easy to check.  You use the Rational Roots Theorem.
A degree-1 factor means you have a rational root, and the Rational
Roots Theorem tells you what those roots could be.  So you try all the
possibilities and see if any work.  If none work, then your polynomial
can't factor into a degree-1 times a degree-4.

For the other form, you suppose that

x^5 + x + 1 = (x^2 + ax + b)*(x^3 + cx^2 + dx + e),

and then you multiply out the right side of the equation and set the
coefficients equal to one another.  That gives you five equations in
five variables.  Sometimes they can be hard to solve, but sometimes
it's easier.  And you can use the fact that all of the variables have
to be integers.  For example,

be = 1

implies that either b = e = +1, or b = e = -1.  That's the only way to
factor the number 1 into two integers.  So try solving these
equations, and see what you get.

You can see another example worked out at

Factoring Quartics
http://mathforum.org/library/drmath/view/56403.html

back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Polynomials

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search