If is the square-free factorization
of **a**, then it is clear that

and hence that **c = ** GCD is

Define

Then **w** has the same roots as **a**, but all are simple. It is
clear that if we define by

then we can find by a simple division:

Thus two GCD calculations get us the factor corresponding to
the simple roots of , and a reduced polynomial whose
form is the same as that of **a** but with one factor removed and all
powers reduced. Applying this process recursively, we are done. (Note
that some improvements can still be made). See the Maple routine
`sqrfree`

for an implementation of this algorithm in Maple.

** Remark**. This factorization is wholly rational. That is, if we
are working with polynomials whose coefficients are rational, then the
factors that we come up with will also have rational coefficients.
It is this that makes Hermite's method useful.

Thu Nov 16 13:46:20 PST 1995