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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.