next up previous
Next: Algorithm for square-free Up: HermiteHorowitz, Rothstein, Previous: HermiteHorowitz, Rothstein,

Square-free factorization.

This lets us reduce the problem from one with repeated roots to one with simple roots.

We say that is square-free if there does not exist another polynomial of degree bigger than 0 such that (recall that c | d means that c divides evenly into d).

The square-free factorization of is


where each is square-free, and the GCD if .

For example, has but otherwise splits a into factors containing the simple roots, the roots of degree 4, and the roots of degree 5.

Remark It is easy to prove that has repeated roots if and only if the GCD . You should prove that for yourself as an exercise, as it is fundamental to the following algorithm for computing the square-free factorization.

Rob Corless
Thu Nov 16 13:46:20 PST 1995