the polynomial GCD

Just as 12 and 18 share a greatest common divisor of 6, two polynomials share a greatest common divisor — the polynomial of highest degree that divides both with no remainder. For x^2 - 1 and x^2 - 2x + 1 the common factor is (x - 1). Finding it is one of the most fundamental operations in computer algebra, because the moment you know the shared factor of two polynomials you can cancel it, factor with it, or simplify a fraction by it.

The method is the Euclidean algorithm, the same idea Euclid used for integers, carried over to polynomials via polynomial long division. To find gcd(a, b) with deg a >= deg b: divide a by b to get a remainder r (of strictly lower degree), then replace the pair (a, b) by (b, r) and repeat. The degrees fall every step, so the remainder eventually hits zero, and the last non-zero remainder is the GCD (usually normalized to be monic). For example gcd(x^2 - 1, x^2 - 2x + 1): subtract to get remainder 2x - 2, then divide x^2 - 2x + 1 by 2x - 2 to get remainder 0 — so the GCD is x - 1. The polynomial GCD is the engine behind cancelling common factors in rational expressions and is the first step inside many factorization and simplification routines.

The polynomial GCD matters because it makes exact cancellation reliable, but it carries the signature warning of symbolic computation. Done naively over the rationals, the coefficients of the intermediate remainders blow up dramatically — a textbook case of expression swell where the GCD of two modest polynomials passes through monstrous intermediate fractions. The standard cures are clever: subresultant algorithms keep coefficient growth controlled, and modular GCD methods compute the answer modulo several primes and reconstruct it, sidestepping the swell entirely. Even an operation this basic must be defended against its own intermediate explosion.