Unit 09 · Algebra I

Polynomials, UFD & Resultants

Polynomials over a field behave remarkably like integers: there is division with remainder, a Euclidean algorithm, and unique factorization into irreducibles. This unit builds that toolkit — it is exactly what Unit 10 needs to analyze characteristic and minimal polynomials.

By the end you can

State and use the division algorithm for polynomials.
Prove the remainder and factor theorems and "at most $n$ roots."
Explain how irreducibility depends on the field.
Use unique factorization and resultants to reason about common roots.
Define the minimal polynomial and prove it divides every annihilator.

Unique factorization and resultants

The course calendar explicitly names unique factorization and resultants because they turn polynomial root questions into algebraic divisibility questions. The point is not just to factor examples; it is to know when two polynomials share information.

Theorem $F[x]$ is a UFD

For a field $F$, every nonzero nonconstant polynomial in $F[x]$ factors into irreducible polynomials, and the factorization is unique up to order and multiplication by nonzero constants. This follows from the Euclidean algorithm, which gives gcds and Bezout identities.

Definition resultant

The resultant $\operatorname{Res}(f,g)$ is a scalar built from the coefficients of $f$ and $g$ whose key property is: $\operatorname{Res}(f,g)=0$ iff $f$ and $g$ have a common root over an algebraic closure of $F$.

Example linear test

For $f(x)=x^2-a$ and $g(x)=x-b$, the polynomials share a root exactly when $f(b)=0$, i.e. $b^2-a=0$. Thus the resultant is zero exactly when $b^2=a$; up to a nonzero scalar convention, it is $b^2-a$.

Why it matters & where it comes from

Why it exists

Eigenvalue theory runs on polynomial arithmetic: eigenvalues are roots of the characteristic polynomial, and diagonalizability is governed by how the minimal polynomial factors. The algebra here is the engine under Unit 10.

In the real world

Polynomial division and factorization over finite fields are the mechanics of Reed–Solomon error correction (QR codes, satellite links) and of the AES field $\mathbb{F}_{2^8}$ inside modern encryption.

Story & open questions

The Fundamental Theorem of Algebra — every nonconstant complex polynomial has a root — resisted proof for a century before Gauss; every known proof uses analysis or topology, not algebra alone. Factoring polynomials fast is still an active algorithmic frontier.

Division with remainder

Theorem Division algorithm

For polynomials $f,g$ over a field $F$ with $g\ne0$, there are unique $q,r$ with $$f=qg+r,\qquad r=0\ \text{ or }\ \deg r<\deg g.$$

Proof idea

Existence: induct on $\deg f$. If $\deg f<\deg g$, take $q=0$, $r=f$. Otherwise subtract the right multiple of $g$ — $\tfrac{a}{b}x^{\deg f-\deg g}\,g$, using that the leading coefficient $b$ of $g$ is invertible — to kill the leading term, and apply the induction hypothesis. This is exactly long division.

Uniqueness: if $q_1g+r_1=q_2g+r_2$, then $(q_1-q_2)g=r_2-r_1$; if $q_1\ne q_2$ the left side has degree $\ge\deg g$, the right side less — impossible. ∎

Example

Divide $f=x^3+2x+1$ by $g=x-1$: long division gives $x^3+2x+1=(x-1)(x^2+x+3)+4$ — quotient $x^2+x+3$, remainder $4$. And indeed $f(1)=4$, as the next theorem predicts.

Roots, factors, and the root count

Theorem Remainder & factor theorems

Dividing $f$ by $x-a$ leaves remainder $f(a)$. Hence $a$ is a root of $f$ iff $(x-a)$ divides $f$.

Proof

$f=q\cdot(x-a)+r$ with $r$ constant (degree $<1$). Evaluate at $x=a$: $f(a)=r$. Both claims follow. ∎

Theorem At most $n$ roots

A nonzero polynomial of degree $n$ over a field has at most $n$ roots.

Proof

Induct on $n$. A root $a$ gives $f=(x-a)q$ with $\deg q=n-1$. Any other root $b$ satisfies $(b-a)q(b)=0$; since $b-a\ne0$ and a field has no zero divisors, $q(b)=0$ — so the remaining roots are roots of $q$, at most $n-1$ of them by induction. ∎

This fails without "field": over $\mathbb{Z}_8$, the quadratic $x^2-1$ has four roots ($1,3,5,7$).

Irreducibility depends on the field

Definition

A nonconstant polynomial is irreducible over $F$ if it cannot be written as a product of two polynomials in $F[x]$ of smaller degree. Like primes for integers, irreducibles give unique factorization in $F[x]$.

Example One polynomial, three fields

Take $f(x)=x^2+1$.

Over $\mathbb{R}$: irreducible — no real roots, and a quadratic with no roots has no linear factor.

Over $\mathbb{C}$: $f=(x-i)(x+i)$ — by the Fundamental Theorem of Algebra every complex polynomial splits into linear factors.

Over $\mathbb{Z}_2$: $f=(x+1)^2$, since $(x+1)^2=x^2+2x+1=x^2+1$ there. Same symbols, different arithmetic, different factorization.

Fact Real irreducibles

Over $\mathbb{R}$ the irreducibles are the linear polynomials and the quadratics with negative discriminant; over $\mathbb{C}$, only the linear ones. This is why real matrices can have "missing" eigenvalues that reappear over $\mathbb{C}$ (Unit 10).

The minimal polynomial

Definition

For a square matrix $A$ (or operator $T$), a polynomial $p$ annihilates $A$ if $p(A)=0$. The minimal polynomial of $A$ is the monic annihilating polynomial of least degree.

Theorem

The minimal polynomial divides every annihilating polynomial — in particular (Unit 10) the characteristic polynomial.

Proof

Let $m$ be minimal and $p$ any annihilator. Divide: $p=qm+r$ with $r=0$ or $\deg r<\deg m$.

Then $r(A)=p(A)-q(A)m(A)=0$. If $r\ne0$, scaling it monic gives an annihilator of smaller degree than $m$ — contradiction. So $r=0$ and $m$ divides $p$. ∎

Why "minimal" earns its keep Two easy anchors: the minimal polynomial of $I$ is $x-1$; of the zero matrix is $x$. In Unit 10 the punchline is that $A$ is diagonalizable exactly when its minimal polynomial splits into distinct linear factors — the cleanest test there is.

Common pitfalls

• The division algorithm needs a field: dividing requires inverting the leading coefficient of $g$.
• "Irreducible" is meaningless until you name the field.
• Unique factorization is up to nonzero scalar multiples; monic factors remove that ambiguity.
• A zero resultant detects a common root over an algebraic closure, not necessarily a root already visible in the original field.
• Degree adds under multiplication: $\deg(fg)=\deg f+\deg g$ — a fact used silently in almost every proof here.
• "At most $n$ roots" counts roots in a field; over rings like $\mathbb{Z}_8$ it fails.

Practice

Original problems written for this guide in the style of Friedberg, Insel & Spence exercises. Write a full solution before opening the answer.

Practice 1 · Long division

Divide $x^3+2x+1$ by $x-1$; give the quotient and remainder.

Solution

Quotient $x^2+x+3$, remainder $4$: check $(x-1)(x^2+x+3)=x^3+2x-3$, and adding $4$ restores $f$. Also $f(1)=4$ — the remainder theorem agrees.

Practice 2 · Factor theorem

Show $x=2$ is a root of $f=x^3-2x^2+x-2$ and factor $f$ over $\mathbb{R}$.

Solution

$f(2)=8-8+2-2=0$; dividing, $f=(x-2)(x^2+1)$, and $x^2+1$ is irreducible over $\mathbb{R}$.

Practice 3 · Root count

Prove a degree-$n$ polynomial over a field has at most $n$ roots.

Solution

Induction with the factor theorem: each root $a$ splits off a factor $(x-a)$, and any other root must be a root of the degree-$(n-1)$ quotient because fields have no zero divisors.

Practice 4 · GCD

Find $\gcd(x^2-1,\ x^3-1)$ over $\mathbb{Q}$.

Solution

$x^2-1=(x-1)(x+1)$ and $x^3-1=(x-1)(x^2+x+1)$. The factors $x+1$ and $x^2+x+1$ share nothing, so the gcd is $x-1$.

Practice 5 · Field dependence

Factor $x^2+1$ over $\mathbb{C}$ and over $\mathbb{Z}_2$.

Answer

$(x-i)(x+i)$ over $\mathbb{C}$; $(x+1)^2$ over $\mathbb{Z}_2$ since $2x=0$ there.

Practice 6 · Remainder theorem

Prove: the remainder when $f$ is divided by $x-a$ is $f(a)$.

Solution

$f=q(x-a)+r$ with $r$ constant; evaluating at $a$ kills the first term and leaves $f(a)=r$.

Practice 7 · Small minimal polynomials

Find the minimal polynomials of $I$, of the zero matrix, and of a projection $P\ne0,I$ with $P^2=P$.

Answer

$x-1$; $x$; and $x^2-x=x(x-1)$ — no smaller monic works because $P\ne0$ rules out $x$ and $P\ne I$ rules out $x-1$. Distinct linear factors: projections are diagonalizable.

Practice 8 · Divisibility

Prove the minimal polynomial divides every polynomial that annihilates $A$.

Solution

Divide $p=qm+r$; then $r(A)=0$ with $\deg r<\deg m$, so minimality forces $r=0$.

Practice 9 · UFD proof sketch

Explain why the Euclidean algorithm in $F[x]$ implies unique factorization.

Solution

The Euclidean algorithm gives gcds and Bezout identities. Those imply Euclid's lemma: if an irreducible $p$ divides $ab$, then $p$ divides $a$ or $b$. Repeatedly applying Euclid's lemma to two factorizations forces the irreducible factors to match up to nonzero constants.

Practice 10 · Resultant meaning

For $f(x)=x^2-2$ and $g(x)=x-b$ over $\mathbb{Q}(b)$, when should $\operatorname{Res}(f,g)$ be zero?

Answer

A linear polynomial $x-b$ shares a root with $f$ exactly when $b$ itself is a root of $f$. So the resultant vanishes exactly when $b^2-2=0$.

Expanded topic checklist

Course coverage. This unit is part of the complete MAT240H1 topic map. It should cover the following items before you move on:

Division algorithm. Use quotient and remainder in $F[x]$ and prove uniqueness.
Factorization. Use irreducibles, gcds, Bezout identities, and unique factorization.
Resultants. Use resultants as a coefficient-based test for common roots.
Minimal polynomials. Relate polynomial arithmetic to operators and matrices.

Textbook/source alignment

Use the current UofT MAT240H1 calendar topics as the coverage spine, and pair lecture notes with a Friedberg-Insel-Spence-style linear algebra text for extra reading. The exact assigned textbook should still be checked against the instructor syllabus.

Core theorem map

The polynomial spine is: Euclidean division gives gcds, gcds give factorization control, and factorization controls eigenvalue and minimal-polynomial behavior.

Study routine. Always name the field: irreducibility, roots, and factorization can change completely when the field changes.

Deep practice extensions

Use these after the main practice set. They are designed to force definition-level reasoning, theorem selection, and mixed application rather than routine calculation only.

Extension 1 · Division

Divide $x^3+1$ by $x+1$ over any field of characteristic not $2$.

Guide

The quotient is $x^2-x+1$ and the remainder is $0$.

Extension 2 · Field dependence

Factor $x^2+1$ over $\mathbb{R}$ and $\mathbb{C}$.

Guide

It is irreducible over $\mathbb{R}$ and equals $(x-i)(x+i)$ over $\mathbb{C}$.

Extension 3 · Resultant idea

What does $\operatorname{Res}(f,g)=0$ tell you?

Guide

It tells you $f$ and $g$ share a root over an algebraic closure, equivalently they have a nontrivial common factor there.

Extension 4 · Minimal polynomial

Why must the minimal polynomial divide every annihilating polynomial?

Guide

Divide the annihilator by the minimal polynomial. Evaluating at the operator leaves a lower-degree annihilator as the remainder, so minimality forces that remainder to be zero.

← Unit 08Determinants Unit 10 →Eigenvalues & diagonalization