Polynomials over a Field

Study Sheet

Polynomials over a Field

Division, roots, irreducibility tests and unique factorization in F[x]

Polynomial Rings and Division

Concept
The ring F[x]F[x] and the division algorithm

For a field FF, F[x]F[x] is the ring of polynomials anxn+⋯+a1x+a0a_nx^n+\cdots+a_1x+a_0 with coefficients in FF. Over a field, deg⁡(fg)=deg⁡f+deg⁡g\deg(fg)=\deg f+\deg g, and the division algorithm holds: for ff and nonzero gg there are unique q,rq,r with f=qg+rf=qg+r and either r=0r=0 or deg⁡r<deg⁡g\deg r<\deg g.

F[x]F[x] behaves remarkably like the integers: there is a "size" (the degree) and long division always works, because the leading coefficient of gg can be inverted in the field. That one fact drives the whole topic — roots, factorization, greatest common divisors. All the polynomial arithmetic uses the field's own operations, so over Zp\mathbb Z_p every coefficient is reduced mod pp as you go.

Example
Long division over Q\mathbb Q

Divide f=x4+3x+1f=x^4+3x+1 by g=x2+1g=x^2+1. The quotient is q=x2−1q=x^2-1: indeed (x2+1)(x2−1)=x4−1(x^2+1)(x^2-1)=x^4-1, and f−(x4−1)=3x+2f-(x^4-1)=3x+2. So x4+3x+1=(x2+1)(x2−1)+(3x+2)x^4+3x+1=(x^2+1)(x^2-1)+(3x+2), with remainder r=3x+2r=3x+2 of degree 1<21<2.

Example
Long division over Z5\mathbb Z_5

In Z5[x]\mathbb Z_5[x] divide x3+2x+1x^3+2x+1 by x+3x+3. The quotient is x2+2x+1x^2+2x+1: (x+3)(x2+2x+1)=x3+5x2+7x+3≡x3+2x+3(x+3)(x^2+2x+1)=x^3+5x^2+7x+3\equiv x^3+2x+3. Subtracting, the remainder is 1−3=−2≡31-3=-2\equiv3. So x3+2x+1=(x+3)(x2+2x+1)+3x^3+2x+1=(x+3)(x^2+2x+1)+3 in Z5[x]\mathbb Z_5[x].

Side note
Where it goes wrong

The degree formula needs a field (or at least no zero divisors). In Z6[x]\mathbb Z_6[x], (2x)(3x)=6x2=0(2x)(3x)=6x^2=0: two degree-11 polynomials multiply to 00. Long division can also fail there — dividing by 2x+12x+1 is fine, but dividing by 2x2x is not, because the leading coefficient 22 has no inverse mod 66.

Try it
Try it: a division in Z2[x]\mathbb Z_2[x]

Divide x3+x+1x^3+x+1 by x+1x+1 in Z2[x]\mathbb Z_2[x].

Show the answer

(x+1)(x2+x)=x3+2x2+x≡x3+x(x+1)(x^2+x)=x^3+2x^2+x\equiv x^3+x, and x3+x+1−(x3+x)=1x^3+x+1-(x^3+x)=1. So the quotient is x2+xx^2+x and the remainder is 1\mathbf1.

Roots and the Factor Theorem

Concept
Remainder and factor theorems

Remainder theorem: dividing ff by x−ax-a leaves remainder f(a)f(a). Factor theorem: x−ax-a divides ff exactly when f(a)=0f(a)=0. Consequently a nonzero polynomial of degree nn over a field has at most nn roots in that field.

Reminder — Remainder and Factor theorems:  P(x)=(x−c)Q(x)+P(c)⟹(x−c)∣P(x)  ⟺  P(c)=0P(x)=(x-c)Q(x)+P(c) \quad\Longrightarrow\quad (x-c)\mid P(x) \iff P(c)=0

Each root aa splits off a factor x−ax-a, lowering the degree by one, so you cannot find more roots than the degree. This "at most nn roots" fact is special to fields (and integral domains): over Z8\mathbb Z_8 the quadratic x2−1x^2-1 has four roots. Over a finite field you can find every root by trying each element; over Q\mathbb Q the rational root test narrows the search.

Example
Roots of x2+1x^2+1 in Z5\mathbb Z_5

Try x=0,1,2,3,4x=0,1,2,3,4: x2+1=1,2,5,10,17≡1,2,0,0,2x^2+1=1,2,5,10,17\equiv1,2,0,0,2. The roots are 22 and 33, so x2+1=(x−2)(x−3)x^2+1=(x-2)(x-3) in Z5[x]\mathbb Z_5[x] — check: (x−2)(x−3)=x2−5x+6≡x2+1(x-2)(x-3)=x^2-5x+6\equiv x^2+1. Over R\mathbb R the same polynomial has no roots at all.

Example
Using the remainder theorem

For f=x3+2x+1f=x^3+2x+1 in Z5[x]\mathbb Z_5[x], the remainder on division by x+3=x−2x+3=x-2 is f(2)=8+4+1=13≡3f(2)=8+4+1=13\equiv3, matching the long division in the previous section without doing it.

Example
Too many roots outside a field

In Z8\mathbb Z_8, x2−1x^2-1 has the roots 1,3,5,71,3,5,7 (each squares to 11: 32=93^2=9, 52=255^2=25, 72=497^2=49, all ≡1(mod8)\equiv1\pmod8). Four roots for a degree-22 polynomial — possible only because Z8\mathbb Z_8 is not a field.

Side note
Where it goes wrong

Having no roots does not make a polynomial "prime". Over R\mathbb R, x4+2x2+1=(x2+1)2x^4+2x^2+1=(x^2+1)^2 has no real roots but factors. The root test only settles irreducibility for degrees 22 and 33, as the next section explains.

Try it
Try it: roots in Z5\mathbb Z_5

Does x3+x+1x^3+x+1 have a root in Z5\mathbb Z_5?

Show the answer

Evaluate at 0,1,2,3,40,1,2,3,4: 1,3,11,31,69≡1,3,1,1,41,3,11,31,69\equiv1,3,1,1,4. None is 00, so no root.

Irreducible Polynomials

Concept
Irreducibility, and the root test in low degree

A non-constant f∈F[x]f\in F[x] is irreducible over FF if it is not a product of two polynomials of smaller degree in F[x]F[x]. A polynomial of degree 22 or 33 is irreducible over FF exactly when it has no root in FF. Over Q\mathbb Q, the rational root test says a root pq\frac pq (in lowest terms) of an integer polynomial has p∣a0p\mid a_0 and q∣anq\mid a_n.

Irreducible polynomials are the "primes" of F[x]F[x]. Whether a polynomial is irreducible depends on the field: x2−2x^2-2 is irreducible over Q\mathbb Q but factors as (x−2)(x+2)(x-\sqrt2)(x+\sqrt2) over R\mathbb R; x2+1x^2+1 is irreducible over R\mathbb R but splits over C\mathbb C and over Z5\mathbb Z_5. The root test works in degree 22 and 33 because any factorization of such a polynomial must include a factor of degree 11, which means a root.

Example
x3−2x^3-2 is irreducible over Q\mathbb Q

By the rational root test, any rational root is one of ±1,±2\pm1,\pm2. But 1−2=−11-2=-1, −1−2=−3-1-2=-3, 8−2=68-2=6, −8−2=−10-8-2=-10 — none is 00. A cubic with no rational root is irreducible over Q\mathbb Q.

Example
The only irreducible quadratic over Z2\mathbb Z_2

The monic quadratics over Z2\mathbb Z_2 are x2x^2, x2+1=(x+1)2x^2+1=(x+1)^2, x2+x=x(x+1)x^2+x=x(x+1) and x2+x+1x^2+x+1. Only x2+x+1x^2+x+1 has no root (0↦10\mapsto1, 1↦3≡11\mapsto3\equiv1), so it is the unique irreducible quadratic over Z2\mathbb Z_2.

Example
No roots, still reducible

x4+4x^4+4 has no real roots, yet x4+4=(x2+2x+2)(x2−2x+2)x^4+4=(x^2+2x+2)(x^2-2x+2) over Q\mathbb Q (Sophie Germain's identity: x4+4=(x2+2)2−(2x)2x^4+4=(x^2+2)^2-(2x)^2). For degree 44 and up, ruling out roots is not enough.

Side note
Where it goes wrong

Two classic slips: applying the root test to a quartic (see x4+4x^4+4), and forgetting which field you are in — "x2+1x^2+1 is irreducible" is true over Q\mathbb Q and R\mathbb R but false over C\mathbb C and over Z5\mathbb Z_5.

Try it
Try it: a cubic over Z2\mathbb Z_2

Is x3+x+1x^3+x+1 irreducible over Z2\mathbb Z_2?

Show the answer

It is a cubic, so check roots: f(0)=1f(0)=1 and f(1)=1+1+1=3≡1f(1)=1+1+1=3\equiv1. No root, so it is irreducible.

Eisenstein's Criterion and Reduction mod p

Concept
Two irreducibility tests over Q\mathbb Q

Eisenstein: if f=anxn+⋯+a0∈Z[x]f=a_nx^n+\cdots+a_0\in\mathbb Z[x] and a prime pp divides a0,…,an−1a_0,\ldots,a_{n-1}, does not divide ana_n, and p2∤a0p^2\nmid a_0, then ff is irreducible over Q\mathbb Q. Reduction mod pp: if p∤anp\nmid a_n and the reduction of ff mod pp is irreducible over Zp\mathbb Z_p (of the same degree), then ff is irreducible over Q\mathbb Q.

These tests handle any degree. Eisenstein needs the right prime and the right shape; when a polynomial does not fit, the substitution x↦x+1x\mapsto x+1 sometimes makes it fit, since f(x)f(x) is irreducible exactly when f(x+1)f(x+1) is. Reduction mod pp turns a question over the infinite field Q\mathbb Q into a finite check over Zp\mathbb Z_p — but only in one direction: a reducible reduction proves nothing.

Example
A quintic by Eisenstein

x5−6x+3x^5-6x+3: the prime 33 divides −6-6 and 33 (and the zero coefficients), does not divide the leading 11, and 9∤39\nmid3. So x5−6x+3x^5-6x+3 is irreducible over Q\mathbb Q.

Example
The shift trick

For Φ5(x)=x4+x3+x2+x+1=x5−1x−1\Phi_5(x)=x^4+x^3+x^2+x+1=\frac{x^5-1}{x-1}, substitute x+1x+1: Φ5(x+1)=(x+1)5−1x=x4+5x3+10x2+10x+5\Phi_5(x+1)=\frac{(x+1)^5-1}{x}=x^4+5x^3+10x^2+10x+5. Eisenstein with p=5p=5 applies (55 divides 5,10,10,55,10,10,5, 25∤525\nmid5), so Φ5\Phi_5 is irreducible over Q\mathbb Q.

Example
Reduction mod 22

For f=x3+4x2+3x+1f=x^3+4x^2+3x+1, reduce mod 22: x3+x+1x^3+x+1, which is irreducible over Z2\mathbb Z_2 (it has no root). The leading coefficient 11 is not even, so ff is irreducible over Q\mathbb Q.

Side note
Where it goes wrong

Eisenstein is one-directional: failing it says nothing. x2+1x^2+1 fits no prime, yet it is irreducible over Q\mathbb Q. Likewise reduction mod pp: x2+1x^2+1 reduces mod 55 to (x−2)(x−3)(x-2)(x-3), which does not show x2+1x^2+1 reducible over Q\mathbb Q.

Try it
Try it: Eisenstein

Show 2x4+9x2+6x+32x^4+9x^2+6x+3 is irreducible over Q\mathbb Q.

Show the answer

Take p=3p=3: 33 divides 9,6,39,6,3 (and the zero x3x^3 coefficient), 3∤23\nmid2, and 9∤39\nmid3. Eisenstein applies, so it is irreducible.

Unique Factorization and the gcd

Concept
F[x]F[x] has unique factorization

Every non-constant polynomial over a field is a product of irreducible polynomials, uniquely up to order and constant factors. The Euclidean algorithm computes gcd⁡(f,g)\gcd(f,g) by repeated division, exactly as for integers.

Unique factorization is why "the" factorization of a polynomial makes sense. It depends on the field: over C\mathbb C every polynomial splits into linear factors (the fundamental theorem of algebra), over R\mathbb R into linear and quadratic factors, and over Q\mathbb Q or Zp\mathbb Z_p irreducible factors can have any degree.

Example
x4−1x^4-1 over four fields

Over Q\mathbb Q and R\mathbb R: x4−1=(x−1)(x+1)(x2+1)x^4-1=(x-1)(x+1)(x^2+1). Over C\mathbb C: (x−1)(x+1)(x−i)(x+i)(x-1)(x+1)(x-i)(x+i). Over Z5\mathbb Z_5: (x−1)(x−2)(x−3)(x−4)(x-1)(x-2)(x-3)(x-4), since 1,2,3,41,2,3,4 are all fourth roots of 11 mod 55 (24=16≡12^4=16\equiv1, 34=81≡13^4=81\equiv1).

Example
A gcd by the Euclidean algorithm

gcd⁡(x6−1,x4−1)\gcd(x^6-1,x^4-1): x6−1=x2(x4−1)+(x2−1)x^6-1=x^2(x^4-1)+(x^2-1), then x4−1=(x2+1)(x2−1)+0x^4-1=(x^2+1)(x^2-1)+0. The last nonzero remainder is x2−1x^2-1, so gcd⁡=x2−1\gcd=x^2-1.

Side note
Where it goes wrong

The gcd is only defined up to a constant factor; we usually make it monic. And factorizations over different fields are different answers to different questions — x2+1x^2+1 is "fully factored" over Q\mathbb Q but not over C\mathbb C.

Try it
Try it: a gcd

Find gcd⁡(x3−1,x2−1)\gcd(x^3-1,x^2-1) over Q\mathbb Q.

Show the answer

x3−1=x(x2−1)+(x−1)x^3-1=x(x^2-1)+(x-1), then x2−1=(x+1)(x−1)x^2-1=(x+1)(x-1). So gcd⁡=x−1\gcd=\mathbf{x-1}.

Why It Works

Induct on n=deg⁡fn=\deg f. If ff has no root we are done. If f(a)=0f(a)=0, the factor theorem gives f=(x−a)gf=(x-a)g with deg⁡g=n−1\deg g=n-1. Any other root b≠ab\ne a satisfies 0=(b−a)g(b)0=(b-a)g(b), and since a field has no zero divisors, g(b)=0g(b)=0. By induction gg has at most n−1n-1 roots, so ff has at most nn.

If ff of degree 22 or 33 factors as ghgh with smaller degrees, the degrees add up to 22 or 33, so one factor has degree 11, say c(x−a)c(x-a). Then f(a)=0f(a)=0. So no root means no factorization.

Suppose f=ghf=gh in Z[x]\mathbb Z[x] (Gauss's lemma lets us assume integer coefficients) with both factors of positive degree. Reduce mod pp: fˉ=aˉnxn\bar f=\bar a_nx^n, so gˉ\bar g and hˉ\bar h are both monomials, gˉ=bxk\bar g=b x^k, hˉ=cxn−k\bar h=c x^{n-k} with k,n−k≥1k,n-k\ge1. Then the constant terms of gg and hh are both divisible by pp, so p2p^2 divides their product a0a_0 — a contradiction.

If deg⁡f<deg⁡g\deg f<\deg g, take q=0q=0, r=fr=f. Otherwise subtract anbmxn−mg\frac{a_n}{b_m}x^{n-m}g from ff (possible because bmb_m, the leading coefficient of gg, is invertible in FF); this kills the leading term, so the degree drops. Repeat until the degree is below deg⁡g\deg g.