Division algorithm, GCD, and irreducibility testing
The polynomial ring F[x] over a field F is one of the most important objects in algebra. Like the integers, it supports a division algorithm, a Euclidean algorithm for computing GCDs, and a notion of irreducibility. Polynomials that cannot be factored play the role of prime numbers.
In this lesson, you will perform polynomial long division, compute GCDs via the Euclidean algorithm, and test polynomials for irreducibility over different fields.
Just as integers can be divided with quotient and remainder, so can polynomials. Given f(x) and g(x) with g ≠ 0, there exist unique q(x) and r(x) such that f = q · g + r with deg(r) < deg(g). Watch the algorithm unfold step by step.
Key insight: The division algorithm makes F[x] a Euclidean domain. This single property implies that F[x] is a PID and a UFD -- every polynomial factors uniquely into irreducibles.
The Euclidean algorithm extends naturally to polynomials. Repeatedly replace the larger polynomial by the remainder of dividing by the smaller, until the remainder is zero. The last nonzero remainder is the GCD. This algorithm is fundamental to factoring polynomials and computing in quotient rings.
Key insight: Two polynomials are coprime (gcd = 1) if and only if they share no common roots. The extended Euclidean algorithm finds polynomials s(x) and t(x) such that s · f + t · g = gcd(f, g).
An irreducible polynomial cannot be factored into polynomials of smaller positive degree. Over the rationals, x² + 1 is irreducible (no real roots), but over F₂ it factors as (x+1)². Irreducibility depends critically on the base field. Test polynomials and see how the same polynomial behaves differently over different fields.
Try x²+1: irreducible over Q and F₃, but reducible over F₂ (since 1²+1=0) and F₅ (since 2²+1=0).
Key insight: A polynomial of degree 2 or 3 is irreducible over a field F if and only if it has no roots in F. For degree 4 and higher, having no roots is necessary but not sufficient -- one must also check for quadratic factors.