Division algorithm, GCD, and irreducibility testing
Polynomials can be divided with remainder, have greatest common divisors, and come in “prime” versions, just like integers. Run the algorithms one step at a time.
Pick a problem and press Next Step or Auto Play. Watch the quotient grow term by term while the remainder’s degree drops below the divisor’s.
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.
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.
Pick a pair and press Next Step to replace the larger polynomial by a remainder each round. The last nonzero remainder is the GCD.
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 in any extension field (equivalently, in an algebraic closure). The extended Euclidean algorithm finds polynomials s(x) and t(x) such that s · f + t · g = gcd(f, g).
Choose a polynomial and a field, then switch fields and watch the verdict change. Try x²+1 over Q and over F₂.
Try x²+1: irreducible over Q and F₃, but reducible over F₂ (since 1²+1=0) and F₅ (since 2²+1=0).
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.
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.
Spot a mistake or have an idea?