What is a polynomial ring?
Take any commutative ring \(R\). A polynomial with coefficients in \(R\) is an expression
\[ a_n x^n + a_{n-1} x^{n-1} + \dots + a_1 x + a_0, \qquad a_i \in R. \]The letter \(x\) is a placeholder, sometimes called an indeterminate. Add polynomials by adding matching coefficients; multiply them by expanding brackets and collecting powers of \(x\), using \(x^i x^j = x^{i+j}\). The result is a new commutative ring, written \(R[x]\).
Example: multiplying in \(\mathbb{Z}[x]\)
\((2x + 1)(x^2 - x + 3) = 2x^3 - 2x^2 + 6x + x^2 - x + 3 = 2x^3 - x^2 + 5x + 3\).
Here's a subtle point that matters a lot. A polynomial is not the same thing as a function. Over \(\mathbb{Z}/2\), the polynomial \(x^2 + x\) gives \(0^2 + 0 = 0\) and \(1^2 + 1 = 2 \equiv 0\). As a function on \(\mathbb{Z}/2\), it's identically zero. But as a polynomial it's not zero: its coefficients are 1, 1, 0.
Why insist on the formal version? Because we'll want to plug in things from bigger rings. Plug a \(2 \times 2\) matrix, or an element of a larger field, into \(x^2 + x\), and the result isn't always zero. The polynomial carries more information than its values on \(R\). (Over infinite fields like \(\mathbb{R}\), the two points of view agree, which is why school maths never needed the distinction.)
Degree and units
The degree of a non-zero polynomial is its highest power of \(x\) with non-zero coefficient; that coefficient is the leading coefficient. A polynomial with leading coefficient 1 is monic. Degree plays the role of "size" for polynomials.
Theorem
If \(R\) is an integral domain, then for non-zero \(f, g \in R[x]\),
\[ \deg(fg) = \deg f + \deg g. \]Consequently \(R[x]\) is an integral domain, and its units are exactly the units of \(R\) (as constant polynomials).
Show proof
If \(f\) has leading term \(ax^m\) and \(g\) has leading term \(bx^n\), then the highest term of \(fg\) is \(abx^{m+n}\), and \(ab \neq 0\) because \(R\) is a domain. So \(fg \neq 0\) and its degree is \(m + n\).
If \(fg = 1\), then \(\deg f + \deg g = 0\), so both have degree 0: they're constants, and constants with \(fg = 1\) are units of \(R\). ∎
Without the domain condition, degrees can collapse. In \((\mathbb{Z}/4)[x]\),
\[ (2x + 1)^2 = 4x^2 + 4x + 1 = 1, \]so \(2x + 1\) is a unit: a non-constant polynomial with an inverse (itself). That can never happen over a field.
Division with remainder
You can divide 17 by 5 to get quotient 3 and remainder 2, with the remainder smaller than 5. Polynomials over a field allow the same thing, with "smaller" meaning "lower degree".
Theorem: the division algorithm
Let \(F\) be a field and \(g \neq 0\) in \(F[x]\). For every \(f \in F[x]\) there are unique polynomials \(q\) (quotient) and \(r\) (remainder) with
\[ f = qg + r, \qquad r = 0 \ \text{ or } \ \deg r < \deg g. \]The method is ordinary long division. At each step, choose the term that matches the current leading term, subtract, and repeat:
Each step needs the leading coefficient of the current polynomial divided by the leading coefficient of \(g\). That's why we need a field (or at least a monic \(g\)). In \(\mathbb{Z}[x]\) you can't divide \(x^2\) by \(2x\) and stay in \(\mathbb{Z}[x]\): the quotient would need \(\tfrac12 x\).
Show proof
Existence. Among all polynomials of the form \(f - qg\), pick one, \(r\), of smallest degree (or \(r = 0\)). If \(\deg r \ge \deg g\), let \(r\) have leading term \(ax^m\) and \(g\) have leading term \(bx^n\). Then \(r - \tfrac ab x^{m-n} g\) is also of the form \(f - q'g\) but has smaller degree, since the leading terms cancel. That contradicts our choice, so \(\deg r < \deg g\).
Uniqueness. If \(qg + r = q'g + r'\), then \((q - q')g = r' - r\). The right side has degree less than \(\deg g\), but if \(q \neq q'\) the left side has degree at least \(\deg g\). So \(q = q'\) and \(r = r'\). ∎
Roots and factors
Look at the long division again. The remainder was 13. Now evaluate: \(3^3 - 2 \cdot 3^2 + 4 = 27 - 18 + 4 = 13\). Not a coincidence.
Theorem: remainder and factor theorems
For \(f \in F[x]\) and \(a \in F\): the remainder when \(f\) is divided by \(x - a\) is \(f(a)\). In particular,
\[ f(a) = 0 \iff (x - a) \text{ divides } f. \]Show proof
Divide: \(f = q \cdot (x - a) + r\), where \(r\) has degree less than 1, so it's a constant. Substitute \(x = a\): \(f(a) = q(a) \cdot 0 + r = r\). ∎
So finding a root is the same as finding a linear factor. Each root peels off one factor and lowers the degree by one, which gives a fundamental limit:
Theorem
Over an integral domain, a non-zero polynomial of degree \(n\) has at most \(n\) roots.
Show proof
Work inside the field of fractions, so we can divide. By induction on \(n\): degree 0 means a non-zero constant, with no roots. If \(f\) has degree \(n\) and a root \(a\), write \(f = (x - a)q\) with \(\deg q = n - 1\). If \(b\) is any other root, then \(0 = f(b) = (b - a)q(b)\), and since \(b - a \neq 0\) and there are no zero divisors, \(q(b) = 0\). So every other root of \(f\) is a root of \(q\), of which there are at most \(n - 1\). ∎
In Unit 3 you saw \(x^2 - 1\) with four roots in \(\mathbb{Z}/8\). That's allowed only because \(\mathbb{Z}/8\) isn't a domain: the step "\((b - a)q(b) = 0\) forces \(q(b) = 0\)" fails.
Going deeper: infinitely many square roots of −1
The proof also needs commutativity. In the quaternions (Unit 11), which form a non-commutative division ring, \(x^2 + 1 = 0\) has the solutions \(i\), \(j\), \(k\), and in fact every \(bi + cj + dk\) with \(b^2 + c^2 + d^2 = 1\): a whole sphere of square roots of \(-1\).
Polynomials over \(\mathbb{Z}/p\)
Over \(\mathbb{Z}/p\) you can test for roots by brute force: try all \(p\) values. Does \(x^2 + 1\) have a root? That is, is there a square root of \(-1\)?
\(p = 5\)\(2^2 = 4 \equiv -1\)
\(p = 7\)no roots at all
\(p = 13\)\(5^2 = 25 \equiv -1\)
Which primes have a square root of \(-1\)? Try a few more and a pattern emerges: \(p = 2, 5, 13, 17, 29, \dots\) do, while \(p = 3, 7, 11, 19, 23, \dots\) don't. The odd primes that work are exactly those that leave remainder 1 on division by 4. Unit 9 explains why, and connects it to writing primes as sums of two squares.
Fermat's little theorem says every \(a \in \mathbb{Z}/p\) satisfies \(a^p = a\). So the polynomial \(x^p - x\) has all \(p\) elements as roots. It has degree \(p\), so by the factor theorem it splits completely:
Going deeper: Wilson's theorem
Divide out the factor \(x\): \(x^{p-1} - 1 = (x - 1)(x - 2)\cdots(x - (p-1))\). Compare constant terms. On the left, \(-1\). On the right, \((-1)^{p-1} \cdot 1 \cdot 2 \cdots (p-1)\), which is \((p-1)!\) when \(p\) is odd. So
\[ (p - 1)! \equiv -1 \pmod p. \]Check: \(4! = 24 = 25 - 1\), and \(6! = 720 = 721 - 1 = 7 \times 103 - 1\). This is Wilson's theorem. It even characterises primes: for composite \(n > 4\), \((n-1)! \equiv 0 \pmod n\).
Irreducible polynomials
Prime numbers are the integers that can't be broken into smaller factors. Polynomials have an exact analogue.
Definition
A non-constant polynomial \(f \in F[x]\) is irreducible over \(F\) if it can't be written as \(f = gh\) with \(g, h\) both of lower degree. Otherwise it's reducible.
Irreducibility depends on the field. The same polynomial can be "prime" in one place and factor in another:
| Polynomial | Irreducible over | Factors over |
|---|---|---|
| \(x^2 - 2\) | \(\mathbb{Q}\) | \(\mathbb{R}\): \((x - \sqrt2)(x + \sqrt2)\) |
| \(x^2 + 1\) | \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{Z}/7\) | \(\mathbb{C}\): \((x - i)(x + i)\); \(\mathbb{Z}/5\): \((x - 2)(x - 3)\) |
| \(x^4 + 4\) | none of \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\) | already \(\mathbb{Q}\): \((x^2 + 2x + 2)(x^2 - 2x + 2)\) |
| any linear \(ax + b\) | every field | never |
The last example in the table is a warning: having no roots doesn't make a polynomial irreducible. \(x^4 + 4\) has no rational roots, yet it splits into two quadratics. For small degrees, though, roots tell the whole story:
Theorem: the root test for degree 2 and 3
A polynomial of degree 2 or 3 over a field is irreducible if and only if it has no root in that field.
Show proof
If \(f = gh\) with both of lower degree, the degrees add up to 2 or 3, so one of them has degree 1: it's \(a(x - c)\), and \(c\) is a root. Conversely, a root \(c\) gives the factor \(x - c\). ∎
Over \(\mathbb{Z}/2\) there are only finitely many polynomials of each degree, so we can sieve them, exactly like the sieve of Eratosthenes for primes. Here are all the monic polynomials of degree 1 to 4:
These irreducible polynomials aren't just curiosities. In Unit 10, \(x^2 + x + 1\) builds a field with 4 elements, and \(x^3 + x + 1\) one with 8. Irreducible polynomials over \(\mathbb{Z}/2\) are also the engine of the error-correcting codes in every phone and hard drive.
Polynomials behave like integers
Over a field \(F\), the ring \(F[x]\) is strikingly similar to \(\mathbb{Z}\). Almost every idea from Unit 2 carries over, with degree in place of size:
| Integers \(\mathbb{Z}\) | Polynomials \(F[x]\) |
|---|---|
| size \(|n|\) | degree \(\deg f\) |
| units \(\pm 1\) | non-zero constants |
| primes | irreducible polynomials |
| division with remainder | long division |
| Euclid's algorithm, gcd | Euclid's algorithm, gcd |
| Bézout: \(ax + by = \gcd\) | Bézout: \(fu + gv = \gcd\) |
| unique prime factorisation | unique factorisation into irreducibles |
| \(\mathbb{Z}/p\) is a field | \(F[x]/(f)\) is a field for irreducible \(f\) (Unit 7) |
Example: \(\gcd(x^3 - 1, x^2 - 1)\) by Euclid's algorithm
Divide: \(x^3 - 1 = x \cdot (x^2 - 1) + (x - 1)\). Then \(x^2 - 1 = (x + 1)(x - 1) + 0\). The last non-zero remainder is the gcd: \(x - 1\). This matches the factorisations \(x^3 - 1 = (x - 1)(x^2 + x + 1)\) and \(x^2 - 1 = (x - 1)(x + 1)\).
Unit 8 explains why these parallels hold: \(\mathbb{Z}\) and \(F[x]\) are both Euclidean domains, and division with remainder is all you need to get gcds and unique factorisation.
Testing irreducibility over \(\mathbb{Q}\)
Over \(\mathbb{Q}\) there are infinitely many candidates, so we need cleverer tests. Three classics:
1. Rational root test. If \(p/q\) (in lowest terms) is a root of \(a_n x^n + \dots + a_0\) with integer coefficients, then \(p\) divides \(a_0\) and \(q\) divides \(a_n\). For example, the only possible rational roots of \(x^3 + x + 1\) are \(\pm 1\). Since \(f(1) = 3\) and \(f(-1) = -1\), there are none, so by the root test it's irreducible over \(\mathbb{Q}\).
2. Reduce modulo a prime. A monic integer polynomial that factors over \(\mathbb{Q}\) also factors over \(\mathbb{Z}\) (this is Gauss's lemma), and then the factorisation survives reduction mod \(p\) with the same degrees. So if the reduction mod \(p\) is irreducible, the original is irreducible over \(\mathbb{Q}\). Take \(x^4 + 3x^3 + 2x + 1\). Modulo 2 it becomes \(x^4 + x^3 + 1\), which is purple in the sieve above. So it's irreducible over \(\mathbb{Q}\), a conclusion that would be painful to reach directly.
3. Eisenstein's criterion. If a prime \(p\) divides every coefficient except the leading one, and \(p^2\) doesn't divide the constant term, the polynomial is irreducible over \(\mathbb{Q}\). For example \(x^5 - 6x + 3\) with \(p = 3\). And \(x^n - 2\) with \(p = 2\) shows there are irreducible polynomials over \(\mathbb{Q}\) of every degree, unlike over \(\mathbb{R}\) where nothing above degree 2 is irreducible.
Going deeper: why Eisenstein works
Suppose \(f = gh\) over \(\mathbb{Z}\) (Gauss's lemma lets us assume integer coefficients) with \(f\) monic. Reduce mod \(p\): all non-leading coefficients vanish, so \(\bar f = x^n\). By unique factorisation in \((\mathbb{Z}/p)[x]\), \(\bar g = x^k\) and \(\bar h = x^{n-k}\), with both \(k, n - k \ge 1\). Then the constant terms of \(g\) and \(h\) are both divisible by \(p\), so the constant term of \(f\) is divisible by \(p^2\), a contradiction.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. Compute \((x^2 + x + 1)(x + 1)\) in \((\mathbb{Z}/2)[x]\).
Show answer
\(x^3 + x^2 + x + x^2 + x + 1 = x^3 + 2x^2 + 2x + 1 = x^3 + 1\). That's the factorisation of \(x^3 + 1\) in the sieve.
2. Divide \(x^4 + 3x^3 + 2x + 1\) by \(x^2 + 1\) over \(\mathbb{Q}\).
Show answer
Quotient \(x^2 + 3x - 1\), remainder \(-x + 2\). Check: \((x^2 + 1)(x^2 + 3x - 1) = x^4 + 3x^3 + 3x - 1\), and adding \(-x + 2\) gives \(x^4 + 3x^3 + 2x + 1\). ✓
3. Without long division, find the remainder when \(x^{100}\) is divided by \(x - 1\), and by \(x + 1\).
Show answer
By the remainder theorem: \(1^{100} = 1\) and \((-1)^{100} = 1\). (In fact the remainder on division by \(x^2 - 1\) is also 1, because both \(x - 1\) and \(x + 1\) divide \(x^{100} - 1\).)
4. Is \(x^2 + x + 1\) irreducible over \(\mathbb{Z}/3\)? Over \(\mathbb{Z}/5\)?
Show answer
Over \(\mathbb{Z}/3\): \(1 + 1 + 1 = 3 \equiv 0\), so 1 is a root and it's reducible: \(x^2 + x + 1 = (x - 1)^2\) mod 3. Over \(\mathbb{Z}/5\): values at 0, 1, 2, 3, 4 are 1, 3, 7≡2, 13≡3, 21≡1. No roots, and it has degree 2, so it's irreducible.
5. Show that \(x^3 - 3x - 1\) is irreducible over \(\mathbb{Q}\).
Show answer
Possible rational roots: \(\pm 1\). \(f(1) = -3\), \(f(-1) = 1\). No rational roots, and it's a cubic, so it's irreducible. (Its real roots are \(2\cos 20°\), \(2\cos 140°\), \(2\cos 260°\), which is why trisecting a 60° angle with ruler and compass is impossible.)
6. Find a polynomial of degree 1 that is a unit in \((\mathbb{Z}/9)[x]\).
Show answer
\(3x + 1\): \((3x + 1)(-3x + 1) = 1 - 9x^2 = 1\). The trick is that \(3\) is nilpotent mod 9 (\(3^2 = 0\)), so the high-degree terms vanish.
Summary and glossary
- \(R[x]\) is the ring of formal polynomials over \(R\). A polynomial is more than the function it defines.
- Over a domain, degrees add, \(R[x]\) is a domain, and its units are the units of \(R\).
- Over a field, polynomials can be divided with remainder, the remainder having lower degree.
- \(f(a)\) is the remainder on dividing by \(x - a\), so roots correspond to linear factors, and a degree-\(n\) polynomial has at most \(n\) roots.
- Irreducible polynomials are the primes of \(F[x]\). In degree 2 or 3, irreducible means no roots.
- Over \(\mathbb{Q}\): the rational root test, reduction mod \(p\), and Eisenstein's criterion.
- \(R[x]\)
- Polynomials in \(x\) with coefficients in \(R\).
- Degree
- The highest power of \(x\) with non-zero coefficient.
- Monic
- Leading coefficient equal to 1.
- Root
- An \(a\) with \(f(a) = 0\); equivalently \((x - a) \mid f\).
- Irreducible
- Non-constant, not a product of two lower-degree polynomials.
- Gauss's lemma
- Integer polynomials that factor over \(\mathbb{Q}\) factor over \(\mathbb{Z}\).
- Eisenstein's criterion
- A prime-divisibility test that guarantees irreducibility over \(\mathbb{Q}\).
- Wilson's theorem
- \((p - 1)! \equiv -1 \pmod p\).