If is the square-free factorization of a, then it is clear that
and hence that c = GCD is
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.