Advanced Polynomial Factoring Methods

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
your question if you mean

  (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
Pari can be downloaded for free at

    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
the Berlekamp algorithm, which you can read about here

  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 

If you have any questions about this or need more help, please write
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/