Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 37 ยท Fields and Polynomial Rings

Polynomial Rings

Study the polynomial ring F[x] over a field, implement the division algorithm over Z_p from scratch, and use it for gcds, roots and the factor theorem.

Polynomials behave a lot like integers: you can add, subtract and multiply them, and you can divide them with remainder. Over a field the resemblance is strong enough that nearly every idea from the integers (gcd, primes, residues mod n) has a polynomial twin. This is the starting point for constructing finite fields.

The ring F[x]

Let F be a field such as โ„š, โ„, โ„‚ or โ„คโ‚‡. The polynomial ring F[x] is the set of expressions

Text
aโ‚€ + aโ‚x + aโ‚‚xยฒ + ... + aโ‚™xโฟ      (each aแตข in F)

with the usual addition and multiplication. The degree of a nonzero polynomial is the largest n with aโ‚™ โ‰  0. The degree of the zero polynomial is left undefined (or -โˆž).

Facts you can rely on, because F has no zero divisors:

  • deg(f g) = deg f + deg g for nonzero f, g.
  • F[x] is an integral domain.
  • The units of F[x] are the nonzero constants.

Over โ„คโ‚† the degree formula fails, because 2x ยท 3x = 6xยฒ = 0. That is a reminder that the coefficients matter.

Division with remainder

Theorem. If f, g are in F[x] and g โ‰  0, there are unique q, r in F[x] with

Text
f = g q + r,    and either r = 0 or deg r < deg g

The proof is the long division algorithm: repeatedly subtract a multiple c x^k g that cancels the leading term of what remains. Each step lowers the degree, so it ends. You need a field here because you must divide by the leading coefficient of g.

Let's implement polynomial arithmetic over โ„คโ‚š from scratch. A polynomial is a list of coefficients from the constant term upward. The result is compared with sympy.

Python Polynomial division over Z_p, 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.

The factor theorem

When you divide f by the linear polynomial x - a, the remainder is a constant, namely f(a). So:

  • f(a) = 0 if and only if (x - a) divides f.
  • A nonzero polynomial of degree n over a field has at most n roots in that field.

The second fact fails over rings with zero divisors: in โ„คโ‚ˆ, the polynomial xยฒ - 1 has four roots 1, 3, 5, 7. It is another reason fields are the natural home for polynomials.

The Euclidean algorithm for polynomials

Since division with remainder works, so does the Euclidean algorithm. The gcd of two polynomials is the monic common divisor of greatest degree. It also generates the ideal (f, g), so F[x] is a principal ideal domain, like โ„ค. We will rely on this when we study irreducible polynomials.

Python Roots and gcd over Z_5

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.

By Fermat's little theorem every element of โ„คโ‚… satisfies aโต = a, so xโต - x has all five elements as roots. That is the largest possible number for degree 5.

Python's % operator and pow(a, p - 2, p) do the modular arithmetic here. The inverse formula a^(p-2) works only for prime p; over โ„คโ‚™ with composite n, many elements have no inverse and division with remainder can fail.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Over a field F, deg(f g) equals...

    Leading coefficients multiply to a nonzero value because F has no zero divisors.
  2. 2. When f is divided by x - a, the remainder is...

    f = (x - a) q + r with r constant; substituting x = a gives r = f(a).
  3. 3. What are the units of F[x] for a field F?

    A unit must have degree 0 because degrees add under multiplication.
  4. 4. A nonzero polynomial of degree 4 over a field has at most how many roots in that field?

    Each root gives a linear factor, and the degree bounds the number of such factors.

Summary

  • F[x] is an integral domain whose units are the nonzero constants, and deg(fg) = deg f + deg g.
  • Division with remainder holds in F[x]: f = g q + r with deg r < deg g.
  • f(a) = 0 iff (x - a) divides f, so a degree-n polynomial has at most n roots.
  • The Euclidean algorithm gives gcds, and F[x] is a principal ideal domain.
  • Over rings with zero divisors, such as โ„คโ‚† or โ„คโ‚ˆ, these rules can fail.

Next: Irreducible Polynomials