Next: Roots of Polynomials Up: Polynomial Algebra and Previous: Resultants and Discriminants.

## The GCD

I have assumed that you know what a GCD (Greatest Common Divisor) is. See for example the treatment in the beginning chapter of Cox et al.'s book `Ideals, Varieties, and Algorithms' if you need a reference, or look in Geddes et. al. `Algorithms for Computer Algebra.' In brief, a greatest common divisor of two polynomials p and q is a polynomial d of maximal degree such that d | p and d | q. Such a polynomial always exists and can be computed by the Euclidean Algorithm. In Geddes et. al. you learn that the naively implemented Euclidean algorithm is far too expensive for even moderate problems, and that efficiency in such a computation is greatly to be desired, and that it is possible.

I suppose this actually deserves some treatment in detail, and I will get back to this if I have time; for now we will just take Maple's (very efficient) gcd routine for granted.

Robert Corless
Wed Feb 28 18:25:56 EST 1996