Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 37 · Fields and Polynomial Rings

Irreducible Polynomials

Learn when a polynomial is irreducible, use the root test for degrees 2 and 3, list irreducibles over Z_2 and count them with a formula, all in Python.

An integer greater than 1 is prime when it cannot be written as a product of two smaller positive integers. Polynomials have the same idea, called irreducible. Irreducible polynomials are the building blocks of polynomial factorization, and they are the key to building new fields.

Definition

A nonconstant polynomial f in F[x] is irreducible over F if it cannot be written as f = g h with g, h in F[x] both of smaller degree than f. Otherwise it is reducible.

Irreducibility depends on the field:

  • x² + 1 is irreducible over ℝ but reducible over ℂ ((x - i)(x + i)).
  • x² - 2 is irreducible over ℚ but reducible over ℝ.
  • x² + 1 over ℤ₂ equals (x + 1)², so it is reducible there.

Every degree-1 polynomial is irreducible. Every nonconstant polynomial factors into irreducibles, and the factorization is unique up to order and nonzero constant factors, just as for the integers.

The root test for small degrees

By the factor theorem, f has a root a in F exactly when (x - a) divides f. So:

  • A polynomial of degree 2 or 3 is irreducible over F if and only if it has no root in F. A reducible one must contain a linear factor (degree 2 splits as 1 + 1, degree 3 as 1 + 2).
  • For degree 4 or more, having no roots is not enough. For example (x² + 1)² over ℝ has no real roots but is reducible.

Over a finite field the root test needs only a loop over the p elements.

A brute-force irreducibility test

Over ℤₚ there are finitely many polynomials of each degree, so you can test irreducibility by trial division: f of degree n is reducible exactly when some monic polynomial of degree between 1 and n/2 divides it. The code below builds the test from scratch and compares it with sympy.

Python Irreducible polynomials over Z2, from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

You should see 1 irreducible of degree 2 (x² + x + 1), 2 of degree 3 (x³ + x + 1 and x³ + x² + 1) and 3 of degree 4. These polynomials are the ones used to build the fields GF(4), GF(8) and GF(16) in the next lesson.

How many irreducibles are there?

The number of monic irreducible polynomials of degree n over a field with q elements is

Text
N(q, n) = (1/n) · Σ μ(d) · q^(n/d)      (sum over the divisors d of n)

where μ is the Möbius function (μ(1) = 1, μ(d) = (-1)^k if d is a product of k distinct primes, and 0 if some prime appears twice). For q = 2, this gives N(2, 2) = 1, N(2, 3) = 2 and N(2, 4) = 3. Notice that N(q, n) is positive for every n: there is always an irreducible of each degree over a finite field.

Python Check the counting formula

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Irreducible means "prime" in F[x]

In ℤ, if a prime p divides a b, it divides a or b. The same holds for irreducible polynomials, thanks to the Euclidean algorithm. Therefore the ideal (f) in F[x] is maximal exactly when f is irreducible, and:

Text
F[x] / (f) is a field   ⇔   f is irreducible over F

This is the tool that builds new fields. The element x + (f) in the quotient is a root of f that did not exist before. You will use it in finite fields and field extensions.

Over the rationals: a few extra tools

For ℚ[x], there are criteria that avoid trying all factors:

  • Gauss's lemma: a polynomial with integer coefficients that factors over ℚ also factors over ℤ with the same degrees.
  • Eisenstein's criterion: if a prime p divides every coefficient except the leading one, p does not divide the leading one and p² does not divide the constant term, then f is irreducible over ℚ. For example x⁵ + 6x + 3 works with p = 3.
  • Reduction mod p: if the reduction of f modulo a prime not dividing its leading coefficient is irreducible, so is f over ℚ.

When a problem asks whether a polynomial is irreducible, check the root test (degrees 2 and 3), then try reducing modulo a small prime, then try Eisenstein, possibly after substituting x → x + 1.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A cubic polynomial over a field F is irreducible exactly when it...

    A reducible cubic must have a linear factor, which means a root in F. Conversely, a root gives a linear factor.
  2. 2. x^2 + 1 over Z2 is...

    (x + 1)^2 = x^2 + 2x + 1 = x^2 + 1 over Z2.
  3. 3. F[x]/(f) is a field if and only if...

    Irreducibility makes (f) a maximal ideal.
  4. 4. How many monic irreducible polynomials of degree 2 exist over Z2?

    Of x^2, x^2+1, x^2+x, x^2+x+1, only x^2+x+1 has no root in Z2.

Summary

  • A nonconstant polynomial is irreducible if it has no factorization into two polynomials of smaller degree; this depends on the field.
  • Degrees 2 and 3: irreducible iff no root. Degree 4 and up need more work.
  • Over ℤₚ, trial division by monic polynomials of degree up to n/2 decides irreducibility.
  • Over a finite field with q elements there is an irreducible polynomial of every degree; the count is (1/n) Σ μ(d) q^(n/d).
  • F[x]/(f) is a field exactly when f is irreducible.

Next: Finite Fields