Factoring Polynomials over Real and Complex Numbers

Date: 07/17/2006 at 16:43:40
From: Anil
Subject: Factoring Polynomials that are irreducible in Q, R, and C

I am having difficulties factoring polynomials into a product of 
polynomials that are irreducible in Q[x], R[x], and C[x].  For 
example, x^4 - 15x^2 - 75.

I'm not sure where to start.  Using the rational root test didn't
bring any results trying +/- 1,3,5,15,25,75.  I looked at the graph on
my calculator and it clearly goes through the x-axis two times.  My
conclusion is that it is irreducible in Q[x], but how do I take this
into R[x] and C[x]?

Date: 07/18/2006 at 08:58:45
From: Doctor Vogler
Subject: Re: Factoring Polynomials that are irreducible in Q, R, and C


Hi Anil,

Thanks for writing to Dr. Math.  The three problems

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

are three very different problems, but I'll talk a little about each.

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

  a(x - r1)(x - r2)...(x - rn)

where n (the number of roots or factors) is the degree of the 
polynomial, a is the leading coefficient (coefficient of x^n), and r1 
through rn are the n complex roots.  Since you generally can't 
represent the roots exactly except by saying something like "the 
third root of the polynomial ____," one usually makes do with a 
decimal approximation, which means you use numerical methods to find 
them, such as Newton's Method (or a graphing calculator).

In case (2), the easiest way is to find all of the complex roots and
then pair up the non-real complex factors and put them into quadratic
factors.  That is, you change

  (x - (r + si))(x - (r - si))

into

  x^2 - (2r)x + (r^2 + s^2)

Every polynomial with real coefficients factors into a product of 
linear factors and quadratic factors over the real numbers.  As in
case (1), 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.  For example, 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:
Any rational root has a numerator that divides the constant term of
your polynomial and a denominator that divides the leading
coefficient.  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 your polynomial equals

  (x^2 + ax + b)*(x^3 + cx^2 + dx + e).

For example, if you wanted to factor x^5 + x + 1, then you set

  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/