Polynomial Rings

Polynomials Over a Ring

Everything in this topic is a re-run of Topic 1. Back in Divisibility and Primes we said what it means for one integer to divide another and isolated the primes as the multiplicative atoms; in GCDs and the Euclidean Algorithm we built the gcd and computed it by repeated division; in Bezouts Identity and the Extended Euclidean Algorithm we wrote the gcd as a combination $ax+by$. We are now going to do the identical sequence with polynomials in place of integers, and almost every proof carries over word for word. The only new ingredient is that we get to choose which ring the coefficients live in, and that choice changes the answers dramatically.

Basically, a polynomial over $R$ is the usual thing you have written since high school, except that the coefficients are elements of $R$ rather than real numbers, and so they add and multiply according to $R$'s rules. Recall from Rings and Fields that "ring" in this course always means commutative unital ring; so $R$ has a $0$, a $1$, and addition, subtraction and multiplication all behave.

The condition $a_n\ne 0$ in the definition is doing real work: it is what makes the degree well defined. You are allowed to write $0x^5+3x^2+1$, but the degree is $2$, not $5$, because the honest leading coefficient is the last nonzero one.

Example. For each polynomial, state the degree, the leading coefficient and the constant term, and say whether it is monic.
(a) $f(x)=5x^3-x^2+7$ in $\mathbb{Z}[x]$.
(b) $g(x)=x^4+2x$ in $\mathbb{Q}[x]$.
(c) $h(x)=3$ in ${\mathbb{Z}}_7[x]$.
(d) $k(x)=3x^2+x+1$ in ${\mathbb{Z}}_3[x]$.
(a) $\mathrm{deg}(f)=3$, leading coefficient $5$, constant term $7$; not monic since $5\ne 1$.
(b) $\mathrm{deg}(g)=4$, leading coefficient $1$, constant term $0$; monic.
(c) $\mathrm{deg}(h)=0$, leading coefficient $3$, constant term $3$; not monic. Constants are perfectly good polynomials, of degree $0$.
(d) This is the trap. In ${\mathbb{Z}}_3$ we have $3=0$, so

$$\begin{array}{rl}k(x)& =3x^2+x+1\\ & =0x^2+x+1\\ & =x+1\text{ in }{\mathbb{Z}}_3[x],\end{array}$$

giving $\mathrm{deg}(k)=1$, leading coefficient $1$, constant term $1$; and it is monic. Therefore, always reduce every coefficient into the ring before reading off the degree; a coefficient that looks nonzero on the page may be $0$ in $R$.

The zero polynomial is the one polynomial with no nonzero coefficient at all, so Definition 7.1 simply does not apply to it and its degree is genuinely undefined. Setting $\mathrm{deg}(0)=-\infty$ is a convention, not a theorem, but it is a convention that buys us two things:

• The rule $\mathrm{deg}(fg)=\mathrm{deg}(f)+\mathrm{deg}(g)$ keeps working, since $-\infty +n=-\infty$ and $0\cdot f=0$.
• The rule $\mathrm{deg}(f+g)\le \max (\mathrm{deg}f,\mathrm{deg}g)$ keeps working when the two polynomials cancel entirely.
• The Division Theorem below can demand $\mathrm{deg}(r)<\mathrm{deg}(g)$ without having to add "or $r=0$" as a separate case, since $-\infty$ is less than everything.

Basically, $-\infty$ is chosen precisely so that every statement we want to make about degrees has no annoying exceptions.

The Ring of Polynomials

Having built polynomials out of a ring, the natural question is whether the collection of them is a ring in its own right; and it is, which is why the whole of Topic 1 will transfer.

Proof. The operations are the familiar ones, written out coefficientwise: for $f(x)={\sum }_i{a}_i{x}^i$ and $g(x)={\sum }_i{b}_i{x}^i$,

$$\begin{array}{rl}f(x)+g(x)& =\sum _i(a_i+b_i)x^i,\\ f(x)g(x)& =\sum _k\left(\sum _{i+j=k}{a}_i{b}_j\right)x^k.\end{array}$$

Every coefficient on the right is built from the $a_i$ and $b_i$ using only addition and multiplication in $R$, so closure under both operations is inherited straight from closure in $R$. In the same way, additive associativity and commutativity hold because they hold for each coefficient separately; and multiplicative associativity, commutativity and distributivity hold because expanding both sides produces the same sums of products $a_i{b}_j$ (or $a_i{b}_j{c}_k$), which then agree by the corresponding axiom in $R$.

That leaves the identities and inverses. The zero polynomial is the additive identity, since adding $0$ to each coefficient changes nothing; the additive inverse of ${\sum }_i{a}_i{x}^i$ is ${\sum }_i(-a_i)x^i$, which lives in $R[x]$ because each $-a_i\in R$; and the constant polynomial $1$ is the multiplicative identity, since multiplying by it leaves every coefficient alone. Hence every axiom for a commutative unital ring holds. $■$

Notice that multiplicative inverses were never mentioned, and for good reason: $R[x]$ is essentially never a field, even when $R$ is. There is no polynomial you can multiply $x$ by to get $1$, for exactly the same degree reason that we are about to make precise. So $\mathbb{Q}[x]$ sits alongside $\mathbb{Z}$ in the hierarchy from Rings and Fields: a perfectly good ring where you can add, subtract and multiply, but not divide.

Example. Find the sum of $x^2+2x+3$ and $3x^3-2x+1$ in $\mathbb{Z}[x]$.
Line up like powers and add the coefficients in $\mathbb{Z}$:

$$\begin{array}{rl}(x^2+2x+3)+(3x^3-2x+1)& =3x^3+x^2+(2-2)x+(3+1)\\ & =3x^3+x^2+4.\end{array}$$

Therefore, the sum is $3x^3+x^2+4$, of degree $3$.

Example. Find the sum of $x^2+2x+3$ and $3x^3-2x+1$ in ${\mathbb{Z}}_3[x]$.
The safest route is to reduce each polynomial mod $3$ first, then add:

$$\begin{array}{rl}{x}^2+2x+3& =x^2+2x,\\ 3x^3-2x+1& =0x^3+x+1\\ & =x+1,\end{array}$$

using $3=0$ and $-2=1$ in ${\mathbb{Z}}_3$. Adding,

$$\begin{array}{rl}(x^2+2x)+(x+1)& =x^2+3x+1\\ & =x^2+1\text{ in }{\mathbb{Z}}_3[x].\end{array}$$

As a check, reducing the $\mathbb{Z}[x]$ answer $3x^3+x^2+4$ mod $3$ gives $x^2+1$ as well. Therefore, the sum is $x^2+1$, of degree $2$.

The degree dropped from $3$ to $2$ purely because of the ring we were working in; $3x^3$ is a genuine cubic term over $\mathbb{Z}$ but is the zero polynomial over ${\mathbb{Z}}_3$. This is the single most common slip in this topic. Never quote the degree of a polynomial without saying which $R[x]$ you are in.

Example. Find the product of $x^2-x+3$ and $2x+1$ in $\mathbb{Z}[x]$.
Expanding term by term,

$$\begin{array}{rl}(x^2-x+3)(2x+1)& =2x^3+x^2-2x^2-x+6x+3\\ & =2x^3+(1-2)x^2+(-1+6)x+3\\ & =2x^3-x^2+5x+3.\end{array}$$

Therefore, the product is $2x^3-x^2+5x+3$, of degree $3=2+1$, as expected.

Example. Find the product of $x^2-x+3$ and $2x+1$ in ${\mathbb{Z}}_3[x]$.
Reduce first: $x^2-x+3=x^2+2x$ and $2x+1$ is already reduced. Then

$$\begin{array}{rl}(x^2+2x)(2x+1)& =2x^3+x^2+4x^2+2x\\ & =2x^3+5x^2+2x\\ & =2x^3+2x^2+2x\text{ in }{\mathbb{Z}}_3[x].\end{array}$$

Reducing the $\mathbb{Z}[x]$ answer instead gives $2x^3-x^2+5x+3=2x^3+2x^2+2x$, which agrees. Therefore, the product is $2x^3+2x^2+2x$. Notice that this time the degree did not drop; ${\mathbb{Z}}_3$ is a field, and in a field the product of the two nonzero leading coefficients ($1$ and $2$) can never be $0$.

The general degree rules are worth stating explicitly, since we lean on them constantly:

$$\boxed{\mathrm{deg}(f+g)\le \max (\mathrm{deg}f,\mathrm{deg}g),\mathrm{deg}(fg)\le \mathrm{deg}(f)+\mathrm{deg}(g),}$$

with equality in the second provided $R$ has no zero divisors (in particular, whenever $R$ is a field). Recall from Rings and Fields that a zero divisor is a nonzero element whose product with some other nonzero element is $0$; if the leading coefficients $a_m$ and $b_n$ satisfy $a_m{b}_n=0$, then the $x^{m+n}$ term of $fg$ vanishes and the degree collapses.

Example. Show that $\mathrm{deg}(fg)<\mathrm{deg}(f)+\mathrm{deg}(g)$ can genuinely happen, by multiplying $2x+1$ and $3x+1$ in ${\mathbb{Z}}_6[x]$.
Both factors have degree $1$, so we would hope for a degree $2$ answer. Expanding,

$$\begin{array}{rl}(2x+1)(3x+1)& =6x^2+2x+3x+1\\ & =6x^2+5x+1\\ & =5x+1\text{ in }{\mathbb{Z}}_6[x],\end{array}$$

since $6=0$ in ${\mathbb{Z}}_6$. Therefore, the product has degree $1<1+1$; the culprit is that $2$ and $3$ are zero divisors in ${\mathbb{Z}}_6$. The clean identity $\mathrm{deg}(fg)=\mathrm{deg}f+\mathrm{deg}g$ is a fact about fields (and about $\mathbb{Z}$), not about all rings.

Units of a Polynomial Ring

Recall from Modular Rings and Units that a unit of a ring is an element with a multiplicative inverse, and that the units are exactly the elements you are allowed to divide by. Since $R[x]$ is a ring, it has units too, and knowing them is essential — the definition of "irreducible" and the non-uniqueness of gcds both hinge on which polynomials are units.

Proof. ($\supseteq$) If $a\in F^{\ast }$, then $a$ is a nonzero constant polynomial and $a^{-1}\in F\subseteq F[x]$ satisfies $a\cdot a^{-1}=1$; so $a\in F[x{]}^{\ast }$.
($\subseteq$) Suppose $f(x)\in F[x{]}^{\ast }$, so $f(x)g(x)=1$ for some $g(x)\in F[x]$. Neither $f$ nor $g$ is the zero polynomial (their product is $1\ne 0$), so both have degree at least $0$. Since $F$ is a field it has no zero divisors, so degrees add exactly:

$$\begin{array}{rl}\mathrm{deg}(f)+\mathrm{deg}(g)& =\mathrm{deg}(fg)\\ & =\mathrm{deg}(1)\\ & =0.\end{array}$$

Two non-negative integers summing to $0$ must both be $0$, so $\mathrm{deg}(f)=\mathrm{deg}(g)=0$; that is, $f=a$ and $g=b$ are constants with $ab=1$ in $F$. Hence $f=a\in F^{\ast }$. $■$

Basically, over a field the only invertible polynomials are the nonzero constants, because multiplying by anything of degree $\ge 1$ pushes the degree up and there is no way to push it back down to $0$.

Example. Find the following unit groups.
(a) $\mathbb{Q}[x{]}^{\ast }$.
(b) $\mathbb{Z}[x{]}^{\ast }$.
(c) ${\mathbb{Z}}_3[x{]}^{\ast }$.
(d) ${\mathbb{Z}}_4[x{]}^{\ast }$.
(a) $\mathbb{Q}$ is a field, so by the fact above, $\mathbb{Q}[x{]}^{\ast }={\mathbb{Q}}^{\ast }=\mathbb{Q}\setminus \{0\}$; every nonzero rational constant, and nothing else.
(b) $\mathbb{Z}$ is not a field, but it has no zero divisors, so the degree argument in the proof still runs verbatim and forces $f=a$, $g=b$ with $ab=1$ in $\mathbb{Z}$. We showed in Rings and Fields that this forces $a=\pm 1$. Therefore $\mathbb{Z}[x{]}^{\ast }={\mathbb{Z}}^{\ast }=\{1,-1\}$.
(c) ${\mathbb{Z}}_3$ is a field (as $3$ is prime), so ${\mathbb{Z}}_3[x{]}^{\ast }={\mathbb{Z}}_3^{\ast }=\{1,2\}$.
(d) ${\mathbb{Z}}_4$ is not a field and it does have a zero divisor, namely $2$, since $2\times 2=4=0$. The degree argument collapses, and the answer is genuinely bigger than ${\mathbb{Z}}_4^{\ast }=\{1,3\}$. Watch what happens to $1+2x$:

$$\begin{array}{rl}(1+2x{)}^2& =1+4x+4x^2\\ & =1+0x+0x^2\\ & =1\text{ in }{\mathbb{Z}}_4[x],\end{array}$$

so $1+2x$ is its own inverse and is therefore a unit of degree $1$. The same trick works with any number of terms: because $2^2=0$ in ${\mathbb{Z}}_4$, every product of two of the "$2$" coefficients dies, and one checks in exactly the same way that

$$(3+2x{)}^2=(1+2x+2x^2{)}^2=(3+2x^2+2x^5{)}^2=1.$$

Therefore

$${\mathbb{Z}}_4[x{]}^{\ast }=\{a_0+a_{1}x+\cdots +a_n{x}^n:a_0\in \{1,3\}\text{ and }{a}_1,\dots ,a_n\in \{0,2\}\},$$

which is an infinite set, one unit for each finite choice of which higher coefficients are $2$.

The condition that $F$ be a field in $F[x{]}^{\ast }=F^{\ast }$ is not decoration; ${\mathbb{Z}}_4[x{]}^{\ast }$ is strictly bigger than ${\mathbb{Z}}_4^{\ast }$ and contains units of every degree. The precise reason is that $2$ is nilpotent in ${\mathbb{Z}}_4$ (some power of it is $0$), and nilpotent coefficients can be attached to any power of $x$ without breaking invertibility. Contrast this with (a)–(c), where the coefficient ring had no zero divisors at all and the unit group stayed as small as possible.

Divisibility and Irreducible Polynomials

Now the parallel with Topic 1 begins in earnest. The definition of divisibility is copied straight from Divisibility and Primes with "integer" replaced by "polynomial".

Example. Show that $(2x+1)\mid (2x^3-x^2+5x+3)$ in $\mathbb{Z}[x]$, and decide whether $2\mid x$ in $\mathbb{Z}[x]$ and in $\mathbb{Q}[x]$.
The first one we have already done: from the product example above,

$$2x^3-x^2+5x+3=(x^2-x+3)(2x+1),$$

and $x^2-x+3\in \mathbb{Z}[x]$, so $(2x+1)\mid (2x^3-x^2+5x+3)$ in $\mathbb{Z}[x]$.
For the second, we need $q(x)$ with $x=2q(x)$, i.e. $q(x)=\frac{1}{2}x$. This is not in $\mathbb{Z}[x]$, so $2\nmid x$ in $\mathbb{Z}[x]$; but $\frac{1}{2}x\in \mathbb{Q}[x]$, so $2\mid x$ in $\mathbb{Q}[x]$. Therefore, divisibility is a statement about the ring, not just about the two polynomials; the same pair can divide in one $R[x]$ and not in another.

Basically, an irreducible polynomial is the polynomial version of a prime: it is not zero, not a unit, and cannot be broken into two genuinely smaller pieces. The first bullet is exactly why $1$ is not counted as a prime integer, transplanted.

The source note adds the practical version over a field.

This is just $F[x{]}^{\ast }=F^{\ast }$ rewritten in terms of degrees: over a field, "is a unit" and "has degree $0$" say the same thing, so "one factor must be a unit" becomes "one factor must be constant". Basically, over a field a polynomial is irreducible exactly when it cannot be written as a product of two polynomials of strictly smaller degree.

Two immediate consequences that you should just know:

• Every polynomial of degree $1$ over a field is irreducible, since $1=\mathrm{deg}f+\mathrm{deg}g$ forces one of the degrees to be $0$.
• A polynomial of degree $2$ or $3$ over a field is irreducible if and only if it has no root in $F$; the only available split is off a linear factor $ax+b$, and over a field that factor contributes the root $-a^{-1}b$. (This fails from degree $4$ onwards, where a polynomial can factorise into two quadratics with no roots at all; see Irreducible Polynomials.)

Example. Determine whether $x^2+1$ is irreducible in $\mathbb{R}[x]$, $\mathbb{C}[x]$, ${\mathbb{Z}}_5[x]$, ${\mathbb{Z}}_3[x]$ and ${\mathbb{Z}}_2[x]$.
It has degree $2$ in every one of these, so we hunt for roots.

• In $\mathbb{R}[x]$: $a^2+1\ge 1>0$ for every real $a$, so there is no root and $x^2+1$ is irreducible.
• In $\mathbb{C}[x]$: $x^2+1=(x+i)(x-i)$, two factors of degree $1$; reducible.
• In ${\mathbb{Z}}_5[x]$: testing $a=0,1,2,3,4$ gives $1,2,0,0,2$, so $2$ and $3$ are roots. Indeed

$$\begin{array}{rl}(x+2)(x+3)& =x^2+5x+6\\ & =x^2+1\text{ in }{\mathbb{Z}}_5[x],\end{array}$$

so it is reducible.

• In ${\mathbb{Z}}_3[x]$: testing $a=0,1,2$ gives $1,2,2$, none of which is $0$; irreducible.
• In ${\mathbb{Z}}_2[x]$: $1^2+1=0$, so $1$ is a root, and $(x+1{)}^2=x^2+2x+1=x^2+1$; reducible (in fact a perfect square).
  Therefore, the very same polynomial is irreducible over $\mathbb{R}$ and ${\mathbb{Z}}_3$ but reducible over $\mathbb{C}$, ${\mathbb{Z}}_5$ and ${\mathbb{Z}}_2$. Irreducibility is never a property of a polynomial on its own; it is a property of a polynomial together with its coefficient ring.

Example. Show that $2x+2$ is irreducible in $\mathbb{Q}[x]$ but reducible in $\mathbb{Z}[x]$.
In $\mathbb{Q}[x]$ it has degree $1$, so it is irreducible by the first consequence above; concretely, $2x+2=2(x+1)$ is a factorisation, but $2\in \mathbb{Q}[x{]}^{\ast }$, so it does not count. In $\mathbb{Z}[x]$ the same factorisation $2x+2=2(x+1)$ is fatal, because $\mathbb{Z}[x{]}^{\ast }=\{\pm 1\}$, so neither $2$ nor $x+1$ is a unit. Therefore $2x+2$ is reducible in $\mathbb{Z}[x]$; notice how shrinking the unit group made more polynomials reducible, which is exactly why the clean theory below is stated only over fields.

This is the Fundamental Theorem of Arithmetic from Divisibility and Primes, with irreducible monic polynomials playing the role of the primes and the constant $c$ playing the role of the sign. The reason we insist the $p_i$ are monic is the same reason we insist primes are positive: without it, $6=2\times 3=(-2)\times (-3)$ would count as two different factorisations, and $x^2-1=(x-1)(x+1)=(2x-2)(\frac{1}{2}x+\frac{1}{2})$ would too. Pulling all the unit "junk" out into a single leading $c$ makes the factorisation genuinely unique.

Example. Write $2x^4-2$ in the form guaranteed by Theorem 7.6, over $\mathbb{Q}$ and then over ${\mathbb{Z}}_5$.
Over $\mathbb{Q}$, factorise by repeated difference of two squares:

$$\begin{array}{rl}2x^4-2& =2(x^4-1)\\ & =2(x^2-1)(x^2+1)\\ & =2(x-1)(x+1)(x^2+1),\end{array}$$

and we checked above that $x^2+1$ is irreducible over $\mathbb{Q}$ (it has no real root, let alone a rational one). All three factors are monic irreducibles, so $c=2$ and $k=3$ with every ${\alpha }_i=1$.
Over ${\mathbb{Z}}_5$, the factor $x^2+1$ splits further into $(x+2)(x+3)$, and $x-1=x+4$, so

$$\begin{array}{rl}2x^4-2& =2(x+4)(x+1)(x+2)(x+3)\text{ in }{\mathbb{Z}}_5[x],\end{array}$$

now with $c=2$ and $k=4$. Therefore, the same polynomial has a three-factor factorisation over $\mathbb{Q}$ and a four-factor one over ${\mathbb{Z}}_5$; enlarging the field can only ever split things further, never fuse them.

The Division Theorem for Polynomials

Everything computational in Topic 1 came out of the Division Theorem for integers. Here is its exact analogue, with "smaller remainder" measured by degree rather than by size.

Note that the zero polynomial can be a remainder, since its degree is $-\infty$; this is the payoff of that convention, and it is exactly the case $r=0$ that says $g\mid f$.

Proof (sketch). Use strong induction on $\mathrm{deg}(f)$. If $\mathrm{deg}(f)<\mathrm{deg}(g)$ there is nothing to do; take $q(x)=0$ and $r(x)=f(x)$. Otherwise write $f(x)=a_m{x}^m+\cdots$ and $g(x)=b_n{x}^n+\cdots$ with $m\ge n$, and kill the leading term of $f$ by subtracting the right multiple of $g$:

$$\begin{array}{rl}\tilde{f}(x)& =f(x)-a_m{b}_n^{-1}{x}^{m-n}g(x).\end{array}$$

The $x^m$ terms cancel exactly, so $\mathrm{deg}(\tilde{f})<m$, and by the inductive hypothesis $\tilde{f}=\tilde{q}g+r$ with $\mathrm{deg}(r)<\mathrm{deg}(g)$. Rearranging gives $f=(a_m{b}_n^{-1}{x}^{m-n}+\tilde{q})g+r$, as required.
For uniqueness, suppose $q_{1}g+r_1=q_{2}g+r_2$ with both remainders of degree less than $\mathrm{deg}(g)$. Then $(q_1-q_2)g=r_2-r_1$; the right-hand side has degree less than $\mathrm{deg}(g)$, while the left-hand side has degree $\mathrm{deg}(q_1-q_2)+\mathrm{deg}(g)\ge \mathrm{deg}(g)$ unless $q_1-q_2=0$. So $q_1=q_2$, and then $r_1=r_2$.
Notice that the only thing the argument ever needed from $F$ was the inverse $b_n^{-1}$ of the leading coefficient of $g$; so the whole proof runs unchanged over any ring $R$ provided that leading coefficient is a unit of $R$. $■$

You cannot divide by an arbitrary polynomial over a ring that is not a field. For instance, in $\mathbb{Z}[x]$ try to divide $x^2$ by $2x+1$: the quotient would have to begin with $\frac{1}{2}x$, which is not in $\mathbb{Z}[x]$, and no choice of integer quotient can leave a remainder of degree $0$. Over $\mathbb{Q}[x]$ it is fine, and over $\mathbb{Z}[x]$ it is fine whenever the divisor is monic, since $1$ is a unit in every ring. This is why "monic" is such a load-bearing word in this topic.

To actually find the quotient and remainder we use either long division or balancing coefficients, exactly as with integers.

Example. Find the quotient and remainder when $2x^4+3x^3+x+5$ is divided by $x^2+2x-3$ (in $\mathbb{Q}[x]$).
Write the dividend with every power present, including the missing $0x^2$, and long divide:

                                  2x^2 -    x +    8
           +-----------------------------------------
x^2+2x-3   | 2x^4 + 3x^3 + 0x^2 +    x +    5
             2x^4 + 4x^3 - 6x^2
             ------------------
                    -x^3 + 6x^2 +    x +    5
                    -x^3 - 2x^2 +   3x
                    ------------------
                           8x^2 -   2x +    5
                           8x^2 +  16x -   24
                           ------------------
                                  -18x +   29

At each stage we divide the current leading term by $x^2$ (the leading term of the divisor), write that down in the quotient, multiply the whole divisor by it, and subtract. The process stops when what is left has degree less than $2$. Reading off the answer, $q(x)=2x^2-x+8$ and $r(x)=-18x+29$. Checking that $q(x)g(x)+r(x)=f(x)$:

$$\begin{array}{rl}(2x^2-x+8)(x^2+2x-3)& =2x^4+4x^3-6x^2-x^3-2x^2+3x+8x^2+16x-24\\ & =2x^4+3x^3+0x^2+19x-24,\\ (2x^4+3x^3+19x-24)+(-18x+29)& =2x^4+3x^3+x+5.✓\end{array}$$

Therefore, the quotient is $2x^2-x+8$ and the remainder is $-18x+29$. Always do this check; it costs one line and catches every sign error in the long division.

Example. Find the quotient and remainder when $x^4+2x^3+2$ is divided by $x^2+1$ in ${\mathbb{Z}}_3[x]$, by balancing coefficients.
Since $\mathrm{deg}(f)=4$ and $\mathrm{deg}(g)=2$, the quotient has degree $2$ and the remainder has degree at most $1$; so write

$$\begin{array}{rl}{x}^4+2x^3+2& =(a{x}^2+bx+c)(x^2+1)+(dx+e)\\ & =a{x}^4+b{x}^3+(a+c)x^2+(b+d)x+(c+e),\end{array}$$

and match coefficients in ${\mathbb{Z}}_3$ starting from the top:

$$\begin{array}{rl}a& =1,\\ b& =2,\\ a+c=0& ⟹c=-1=2,\\ b+d=0& ⟹d=-2=1,\\ c+e=2& ⟹e=2-2=0.\end{array}$$

Therefore, $q(x)=x^2+2x+2$ and $r(x)=x$. Checking,

$$\begin{array}{rl}(x^2+2x+2)(x^2+1)+x& =x^4+2x^3+2x^2+x^2+2x+2+x\\ & =x^4+2x^3+3x^2+3x+2\\ & =x^4+2x^3+2\text{ in }{\mathbb{Z}}_3[x].✓\end{array}$$

Balancing coefficients is often faster than long division when the divisor is short and the field is small, because you never have to write out the intermediate subtractions.

Greatest Common Divisors of Polynomials

With division in hand we can copy the gcd definition across from GCDs and the Euclidean Algorithm. There is one genuine new wrinkle, and it is worth meeting head-on.

Notice that "greatest" has been replaced by a divisibility condition rather than an inequality; there is no sensible way to say one polynomial is bigger than another, so we say instead that $d(x)$ is the common divisor that every other common divisor divides into. (For integers these two descriptions agree, which is why you may not have noticed the distinction before.)

The wrinkle is that with this definition there is usually more than one greatest common divisor, because any unit multiple of a GCD is again a GCD.

Example. Find all the GCDs of $f(x)=2x^2+x$ and $g(x)=x^2+4x+3$ in ${\mathbb{Z}}_5[x]$.
Factorise each polynomial, remembering that ${\mathbb{Z}}_5[x{]}^{\ast }={\mathbb{Z}}_5^{\ast }=\{1,2,3,4\}$, so each factorisation can be rewritten in four ways by moving a unit across:

$$\begin{array}{rl}f(x)& =x(2x+1)=2x(x+3)=3x(4x+2)=4x(3x+4),\\ g(x)& =(x+1)(x+3)=(2x+2)(3x+4)=(3x+3)(2x+1)=(4x+4)(4x+2).\end{array}$$

(As a spot check, $2x(x+3)=2x^2+6x=2x^2+x$ and $(3x+3)(2x+1)=6x^2+3x+6x+3=x^2+4x+3$ in ${\mathbb{Z}}_5[x]$.) Comparing the two lists, the common non-constant factors are $2x+1$, $x+3$, $4x+2$ and $3x+4$; and these four are exactly the unit multiples of one another, since

$$\begin{array}{rl}1(x+3)& =x+3,\\ 2(x+3)& =2x+6=2x+1,\\ 3(x+3)& =3x+9=3x+4,\\ 4(x+3)& =4x+12=4x+2\text{ in }{\mathbb{Z}}_5[x].\end{array}$$

Therefore, the GCDs of $f(x)$ and $g(x)$ in ${\mathbb{Z}}_5[x]$ are $2x+1$, $x+3$, $4x+2$ and $3x+4$; four different answers, all equally valid under Definition 7.8.

That is unusable as a function, so we fix a representative. Exactly one of the four is monic.

For example, in ${\mathbb{Z}}_5[x]$ we have $\gcd (2x^2+x,x^2+4x+3)=x+3$.

Basically, "divide by the leading coefficient at the end" is the polynomial version of "take the positive one", which is how we made $\gcd$ single-valued for integers. If your final answer to a gcd question is not monic, you have not finished; multiply through by the inverse of the leading coefficient. By $F[x{]}^{\ast }=F^{\ast }$ this is always possible and never changes which polynomial you have up to units, because the leading coefficient of a nonzero polynomial over a field is always invertible.

The Euclidean Algorithm for Polynomials

Since the Division Theorem holds and degrees are non-negative integers that strictly decrease, the Euclidean algorithm transfers immediately; the degree of the remainder plays the role that the size of the remainder played for integers, and it cannot decrease forever.

Note that when working over polynomial rings we can always factor out any unit from a remainder before applying the Division Theorem to it. For example, if in ${\mathbb{Z}}_3[x]$ we find a remainder $2x+1$ at one step, we could instead multiply it by $2$ to get

$$2(2x+1)=4x+2=x+2\text{ in }{\mathbb{Z}}_3[x],$$

and use $x+2$ as the subject of the next step. This is legitimate because unit multiples have exactly the same divisors, so the set of common divisors never changes. This tip is not optional in practice; scaling each remainder to be monic keeps the fractions under control in $\mathbb{Q}[x]$ and is the difference between a two-line computation and a page of thirds and sevenths.

The one thing to remember is that the algorithm delivers a GCD, whichever one happens to fall out of the arithmetic; you then scale it to be monic to get the standard one.

Example. Let $f(x)=x^4+x^2-2x-4$ and $g(x)=x^3+x^2+2x+2$. Find $\gcd (f(x),g(x))$ in $\mathbb{Q}[x]$.
Divide $f$ by $g$. Since $x^4÷x^3=x$,

$$\begin{array}{rl}f(x)-xg(x)& =(x^4+x^2-2x-4)-(x^4+x^3+2x^2+2x)\\ & =-x^3-x^2-4x-4,\end{array}$$

and then $-x^3÷x^3=-1$, so

$$\begin{array}{rl}(-x^3-x^2-4x-4)+g(x)& =(-x^3-x^2-4x-4)+(x^3+x^2+2x+2)\\ & =-2x-2.\end{array}$$

So the first line of the algorithm is

$$\begin{array}{rlrl}{x}^4+x^2-2x-4& =(x-1)(x^3+x^2+2x+2)+(-2x-2).& & (1)\end{array}$$

The remainder $-2x-2$ has degree $1<3$, as required. Before continuing, scale it by the unit $-\frac{1}{2}$ to get the monic $x+1$, and divide $g$ by that:

$$\begin{array}{rlrl}{x}^3+x^2+2x+2& =x^2(x+1)+2(x+1)& & \\ & =(x^2+2)(x+1)+0.& & (2)\end{array}$$

The remainder is $0$, so the algorithm stops and the last nonzero remainder $x+1$ is a GCD; it is already monic. Therefore, $\gcd (f(x),g(x))=x+1$. As a sanity check, $f(-1)=1+1+2-4=0$ and $g(-1)=-1+1-2+2=0$, so $x+1$ really does divide both.

Example. Find $\gcd (x^3-1,x^2-1)$ in $\mathbb{Q}[x]$.
Running the algorithm,

$$\begin{array}{rl}{x}^3-1& =x(x^2-1)+(x-1),\\ x^2-1& =(x+1)(x-1)+0,\end{array}$$

so the last nonzero remainder is $x-1$, which is monic. Therefore, $\gcd (x^3-1,x^2-1)=x-1$. This matches the factorisations $x^3-1=(x-1)(x^2+x+1)$ and $x^2-1=(x-1)(x+1)$, where $x^2+x+1$ and $x+1$ share nothing.

Bézout's Identity for Polynomials

And finally the identity from Bezouts Identity and the Extended Euclidean Algorithm, transplanted.

We can find these polynomials $p(x)$ and $q(x)$ the same way as we did before with integers: either by reversing the Euclidean algorithm applied to $f(x)$ and $g(x)$, or by using the extended Euclidean algorithm table. The proof is the same as well — run the algorithm, then substitute each remainder upwards until only $f$ and $g$ remain.

Example. Let $f(x)=x^4+x^2-2x-4$ and $g(x)=x^3+x^2+2x+2$. Find $p(x),q(x)\in \mathbb{Q}[x]$ such that $\gcd (f(x),g(x))=f(x)p(x)+g(x)q(x)$.
We know from the previous section that $\gcd (f,g)=x+1$, and line $(1)$ of that run is the only line with a nonzero remainder, so there is only one substitution to make. Rearranging $(1)$ for its remainder,

$$\begin{array}{rlrl}-2x-2& =f(x)-(x-1)g(x).& & \text{(from }(1))\end{array}$$

Now multiply through by $-\frac{1}{2}$ to turn the left-hand side into the monic gcd:

$$\begin{array}{rl}x+1& =-\frac{1}{2}\left(f(x)-(x-1)g(x)\right)\\ & =-\frac{1}{2}f(x)+\frac{1}{2}(x-1)g(x).\end{array}$$

Therefore, $p(x)=-\frac{1}{2}$ and $q(x)=\frac{x-1}{2}$. Checking by expanding, and using $(x-1)(x^3+x^2+2x+2)=x^4+x^2-2$:

$$\begin{array}{rl}f(x)p(x)+g(x)q(x)& =\frac{1}{2}\left[-(x^4+x^2-2x-4)+(x^4+x^2-2)\right]\\ & =\frac{1}{2}\left[2x+2\right]\\ & =x+1.✓\end{array}$$

Notice that $p(x)$ is allowed to be a constant, and that constants like $-\frac{1}{2}$ are unavoidable here; the whole point of working over a field is that these fractions are legal. Over $\mathbb{Z}[x]$ this identity would be impossible to write down.

The Extended Euclidean Table for Polynomials

Back-substitution is fine for a one-line run, but it gets ugly fast; the table from Bezouts Identity and the Extended Euclidean Algorithm works verbatim, with polynomials in every cell. The only change is cosmetic: the letters $x$ and $y$ are taken (they were the row names before, and $x$ is now the variable), so we will call the two coefficient rows $u_i$ and $v_i$, and the invariant becomes

$$\boxed{r_i(x)=f(x)u_i(x)+g(x)v_i(x)\text{ in every column},}$$

with the same recursions $r_i=r_{i-2}-q_i{r}_{i-1}$, $u_i=u_{i-2}-q_i{u}_{i-1}$ and $v_i=v_{i-2}-q_i{v}_{i-1}$, seeded by $u:1,0$ and $v:0,1$.

Example. Redo the previous example with the extended Euclidean algorithm table.
The table must use the unscaled remainders, so we divide $g(x)$ by $-2x-2$ rather than by $x+1$; the quotient there is $-\frac{1}{2}{x}^2-1$, since

$$\begin{array}{rl}\left(-\frac{1}{2}{x}^2-1\right)(-2x-2)& =x^3+x^2+2x+2\\ & =g(x),\end{array}$$

with remainder $0$. So the quotients are $x-1$ and $-\frac{1}{2}{x}^2-1$, and the table is:

For instance the third column comes from $u_3=1-(x-1)\cdot 0=1$ and $v_3=0-(x-1)\cdot 1=1-x$. Reading off the second-last column, where $r_i$ is a GCD,

$$\begin{array}{rl}-2x-2& =f(x)\cdot 1+g(x)(1-x),\end{array}$$

and multiplying by $-\frac{1}{2}$ to make it monic gives $x+1=-\frac{1}{2}f(x)+\frac{x-1}{2}g(x)$, exactly as before. Therefore, $p(x)=-\frac{1}{2}$ and $q(x)=\frac{x-1}{2}$. The table hands you a GCD, not the standard GCD; scaling to monic is always the last step, and you must scale $p(x)$ and $q(x)$ by the same unit.

Example. Let $f(x)=x^4+x^2+2$ and $g(x)=x^2+2x+2$. Find $\gcd (f(x),g(x))$ in ${\mathbb{Z}}_3[x]$, and find some $p(x),q(x)\in {\mathbb{Z}}_3[x]$ such that $\gcd (f(x),g(x))=f(x)p(x)+g(x)q(x)$.
Run the Euclidean algorithm, doing all coefficient arithmetic in ${\mathbb{Z}}_3$. Dividing $f$ by $g$: first $x^4÷x^2=x^2$, and

$$\begin{array}{rl}f(x)-x^{2}g(x)& =(x^4+x^2+2)-(x^4+2x^3+2x^2)\\ & =-2x^3-x^2+2\\ & =x^3+2x^2+2,\end{array}$$

then $x^3÷x^2=x$, and

$$\begin{array}{rl}(x^3+2x^2+2)-xg(x)& =(x^3+2x^2+2)-(x^3+2x^2+2x)\\ & =-2x+2\\ & =x+2.\end{array}$$

So the algorithm reads

$$\begin{array}{rlrl}{x}^4+x^2+2& =(x^2+x)(x^2+2x+2)+(x+2),& & (1)\\ x^2+2x+2& =x(x+2)+2,& & (2)\\ x+2& =(2x+1)\cdot 2+0,& & (3)\end{array}$$