Polynomial Arithmetic

The fifth unit of a rings-first abstract algebra course. Polynomials with coefficients in a ring form a ring; over a field they have a division algorithm, greatest common divisors computed by the Euclidean algorithm, Bezout's identity and unique factorization into irreducible polynomials, each proved in parallel with the integers. Roots and linear factors, and tests for irreducibility over finite fields, the rationals, the reals and the complex numbers, with one quartic followed through every field.

The first unit of the course found $\gcd(1729, 1001) = 91$ in five divisions, wrote 91 as a combination of the two numbers, and saw the answer again in the prime factorizations $1729 = 7 \cdot 13 \cdot 19$ and $1001 = 7 \cdot 11 \cdot 13$. Now take two polynomials with rational coefficients,

$$f(x) = x^4 + x^3 - x^2 - 2x - 2, \qquad g(x) = x^4 - 2x^2 - 3x - 2.$$

Do they have a greatest common divisor, can the Euclidean algorithm find it, and do they factor into "primes" in only one way?

They do, and the answer to all three is the same theory told again. Polynomials over a field have a division algorithm, greatest common divisors, Bezout's identity and unique factorization. The proofs follow the integer proofs step by step, with one systematic translation:

  • the size of a number becomes the degree of a polynomial;
  • the units $\pm 1$ become the nonzero constants;
  • positive integers become monic polynomials, those with leading coefficient 1;
  • primes become irreducible polynomials, the ones that are not a product of two polynomials of lower degree.

For the pair above, three divisions give $\gcd(f, g) = x^2 + x + 1$, and the factorizations $f = (x^2 - 2)(x^2 + x + 1)$ and $g = (x - 2)(x + 1)(x^2 + x + 1)$ confirm it.

One difference has no counterpart among the integers: whether a polynomial is irreducible depends on the field of coefficients. The quartic $f$ runs through the whole unit to show this. It has no rational roots, yet it factors over the rationals. It splits further over the reals, completely over the complex numbers, and differently again modulo each small prime.

The route

The unit has three steps.

  1. First, what a polynomial is. Polynomials with coefficients in any ring form a ring, and the coefficient ring decides how they behave: over an integral domain degrees add and only constants are invertible, but over $\mathbb{Z}_{12}$ degrees need not add, and a polynomial of degree 1 can have an inverse.
  2. Then, division. Over a field, division with remainder always works, and the theory of divisibility from Arithmetic in the Integers carries over.
  3. Finally, the primes: irreducible polynomials, unique factorization, roots, and tests for irreducibility over each field.

The unit covers Chapter 4 of the course text (Hungerford, 2014), §§4.1 to 4.6, with Judson (2026, Chapter 17) as a free companion. The class sessions treated polynomial rings and the division algorithm (§4.1) and then moved to congruence modulo a polynomial. The rest of the chapter is used throughout the later units, so it is developed here in full: divisibility, unique factorization and the irreducibility tests.

Articles

  • Polynomial Rings: what exactly is $x$, and why can two nonzero polynomials multiply to zero? The article defines polynomials as sequences with finitely many nonzero terms and proves that they form a ring. It shows that degrees add under multiplication over an integral domain but not over $\mathbb{Z}_{12}$. It finds the units of $R[x]$ and shows why $F[x]$ is never a field, with a unit of degree 1 in $\mathbb{Z}_{12}[x]$ and power series by contrast. It ends with evaluation, why evaluation needs commutative coefficients, $x^6$ and $x^2$, two different polynomials with the same function on $\mathbb{Z}_5$, and polynomials in several indeterminates.
  • Polynomial Division over a Field: when can one polynomial be divided by another with a smaller remainder, and what follows? The division algorithm holds for any divisor whose leading coefficient is invertible, and its proof of existence and uniqueness is the integer proof with degree in place of size. Long division is the proof run as a procedure, and it explains why $\mathbb{Z}[x]$ has no general division. The article then builds divisibility and associates, the greatest common divisor through the Euclidean algorithm, Bezout's identity and the extended algorithm, and cancellation for relatively prime polynomials. It closes with why enlarging the field never changes a gcd while reducing modulo a prime can.
  • Irreducible Polynomials and Roots: which polynomials are the primes, and how can we tell? The article proves Euclid's lemma and unique factorization in $F[x]$, and the remainder and factor theorems. It shows that a polynomial of degree $n$ has at most $n$ roots, and how that fails in $\mathbb{Z}_{15}$. It factors $x^p - x$ into all the linear factors over $\mathbb{Z}_p$, with Wilson's theorem as a corollary. Then come the tests: roots in degrees 2 and 3, and over the rationals the rational root test, Gauss's lemma, Eisenstein's criterion and reduction modulo a prime, with counts of irreducibles over $\mathbb{Z}_2$ and $\mathbb{Z}_3$. The fundamental theorem of algebra settles the reals and the complex numbers.

Parallels with the integers

In $\mathbb{Z}$ In $F[x]$
division algorithm: $a = bq + r$, $0 \le r < b$ division algorithm: $a = bq + r$, $r = 0$ or $\deg r < \deg b$
Euclidean algorithm and Bezout's identity the same algorithm and identity, with the last remainder made monic
$\gcd(1729, 1001) = 91 = 1729 \cdot (-4) + 1001 \cdot 7$ $\gcd(f, g) = x^2 + x + 1 = \tfrac{x - 1}{2} f - \tfrac{x}{2} g$
Euclid's lemma and unique factorization into primes Euclid's lemma and unique factorization into irreducibles
units $\pm 1$; positive integers nonzero constants; monic polynomials

The integer results are in the division algorithm, divisibility and the Euclidean algorithm and the fundamental theorem of arithmetic. The articles of this unit link to them rather than repeat them, and set out each polynomial proof in the same order as its integer twin so that the two can be read side by side.

The unit applies the language of Rings. Polynomial rings are new rings built from old ones, and whether the coefficients form an integral domain or a field decides which theorems hold. The previous unit, Public-Key Cryptography, supplies Fermat's little theorem, which explains why $x^p - x$ vanishes on $\mathbb{Z}_p$.

The next unit, congruence in polynomial rings and field extensions, does for polynomials what congruence modulo $n$ did for integers. An irreducible polynomial plays the part of a prime modulus, and the classes modulo it form a new field.

References

  • Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), Chapter 4. Brooks/Cole, Cengage Learning. The course text. record · 44 pages
  • Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), Chapter 17. Free online at judsonbooks.org. record · 44 pages