Divide $a(x) = x^4 + 2x^3 - x + 3$ by $b(x) = 2x^2 + x - 1$, with rational coefficients, by the long division taught in school. The first term of the quotient must turn $2x^2$ into $x^4$, so it is $\tfrac{1}{2}x^2$; subtracting $\tfrac{1}{2}x^2 \cdot b(x)$ leaves $\tfrac{3}{2}x^3 + \tfrac{1}{2}x^2 - x + 3$. Two more steps finish the job, and the outcome is
$$x^4 + 2x^3 - x + 3 = (2x^2 + x - 1)\Big(\tfrac{1}{2}x^2 + \tfrac{3}{4}x - \tfrac{1}{8}\Big) + \Big({-\tfrac{1}{8}}x + \tfrac{23}{8}\Big).$$
The remainder has degree 1, less than the degree 2 of the divisor, just as the remainder in $100 = 12 \cdot 8 + 4$ is less than 12. The denominators 2, 4 and 8 appear because every step divides by the leading coefficient 2 of $b(x)$. With integer coefficients that division is impossible, and so is this division with remainder: no quotient in $\mathbb{Z}[x]$ can even produce the leading term $x^4$, since $2c = 1$ has no integer solution $c$. So when does division with a smaller remainder work, and how much of the arithmetic of the integers comes with it?
The division algorithm for polynomials says that over a field, division with remainder always works and has a unique answer. The rest of the article builds on it, as the division algorithm and divisibility and the Euclidean algorithm did for the integers 1729 and 1001. The proofs follow the integer proofs in order, with degree in place of size.
First we prove the theorem, which long division runs as a procedure. Then the Euclidean algorithm finds the gcd of the unit's running pair of quartics, and run backwards it gives Bezout's identity and cancellation. Finally we ask whether the gcd depends on the field. The article assumes Polynomial Rings, especially the degree of a product. It is the second of Polynomial Arithmetic in the MTH 532 notes, and it covers Theorem 4.6 of §4.1 and all of §4.2 of the course text (Hungerford, 2014).
The theorem
The proof needs one fact about degrees that holds even when the coefficients have zero divisors, provided the leading coefficient of one factor is invertible. In plain words, multiplying an invertible leading coefficient by anything nonzero never gives 0, so the top term of the product survives. Throughout, $R$ is a commutative ring with identity.
Lemma. Let $b(x) \in R[x]$ be a nonzero polynomial whose leading coefficient $u$ is a unit of $R$. For every nonzero $k(x) \in R[x]$, the product $b(x)k(x)$ is nonzero and
$$\deg\big(b(x)k(x)\big) = \deg b(x) + \deg k(x).$$
Proof. By the degree proposition, the coefficient of $x^{\deg b + \deg k}$ in $bk$ is $uc$, where $c \neq 0$ is the leading coefficient of $k$, and it is enough to show $uc \neq 0$. If $uc = 0$, then $c = u^{-1}(uc) = u^{-1} \cdot 0 = 0$, a contradiction. $\blacksquare$
Over an integral domain the lemma holds for every nonzero $b(x)$; here it holds even in $\mathbb{Z}_{12}[x]$, as long as $b(x)$ has a leading coefficient such as 1, 5, 7 or 11.
Theorem (division algorithm). Let $a(x), b(x) \in R[x]$ with $b(x) \neq 0$, and suppose the leading coefficient of $b(x)$ is a unit of $R$. There exist unique polynomials $q(x)$ and $r(x)$ in $R[x]$ such that
$$a(x) = b(x)q(x) + r(x), \qquad \text{where either } r(x) = 0 \text{ or } \deg r(x) < \deg b(x).$$
In particular, if $F$ is a field, this holds for every nonzero divisor $b(x) \in F[x]$, since every nonzero element of a field is a unit.
As with integers, $q(x)$ is the quotient and $r(x)$ the remainder. The condition on the remainder replaces $0 \le r < b$, and the case $r(x) = 0$ is listed separately because the zero polynomial has no degree. Write $n = \deg b(x)$ and let $u$ be its leading coefficient.
Here is the plan of the proof. Among the candidate remainders $a - bk$, take one of least degree. If its degree were still $n$ or more, subtracting one more multiple of $b$ would cancel its leading term and give a smaller one. Uniqueness compares degrees.
Proof of existence. Consider the set of candidate remainders
$$S = \{\, a(x) - b(x)k(x) : k(x) \in R[x] \,\}.$$
If $S$ contains the zero polynomial, say $a - bk = 0$, then $q = k$ and $r = 0$ work. Otherwise every element of $S$ is nonzero and has a degree. The degrees form a nonempty set of nonnegative integers, which by the well-ordering principle has a least element. Choose $q(x)$ so that $r(x) = a(x) - b(x)q(x)$ has this least degree, $s$.
Suppose, for contradiction, that $s \ge n$. Let $c$ be the leading coefficient of $r(x)$, and let $t(x) = cu^{-1}x^{s - n}$, a polynomial because $s - n \ge 0$. The product $b(x)t(x)$ has degree $n + (s - n) = s$ and leading coefficient $u \cdot cu^{-1} = c$. So $r(x)$ and $b(x)t(x)$ have the same degree and the same leading coefficient, and their difference
$$r(x) - b(x)t(x) = a(x) - b(x)\big(q(x) + t(x)\big)$$
is either 0 or of degree less than $s$. It belongs to $S$, which by assumption does not contain 0, so it has degree less than $s$. That contradicts the choice of $s$ as the least degree in $S$. Hence $s < n$, and $a = bq + r$ with $\deg r < \deg b$. $\blacksquare$
Proof of uniqueness. Suppose $a = bq + r = bq' + r'$, where each of $r$ and $r'$ is either 0 or of degree less than $n$. Subtracting,
$$b(x)\big(q(x) - q'(x)\big) = r'(x) - r(x).$$
The right side is either 0 or of degree less than $n$, because a difference of two polynomials of degree less than $n$ has all its coefficients from position $n$ onward equal to 0. If $q \neq q'$, the lemma says the left side is nonzero of degree $n + \deg(q - q') \ge n$, which is impossible. So $q = q'$, and then $r' - r = b \cdot 0 = 0$, so $r = r'$. $\blacksquare$
The integer proof makes the same moves, with well-ordering applied to sizes instead of degrees. It subtracts $b$. This proof subtracts the multiple $cu^{-1}x^{s-n}\,b(x)$ chosen to cancel the leading term, and that is where the inverse $u^{-1}$ is needed. Uniqueness in both cases compares the size of $b(q - q')$ with the size of a difference of remainders.
The theorem is Hungerford's Theorem 4.6 for fields, and Judson's Theorem 17.2.1. The class sessions of the course stated it in the form given here, for a divisor with invertible leading coefficient over a commutative ring with identity. That form has a use beyond fields: in $\mathbb{Z}[x]$, division by any monic polynomial works. Dividing the opening example $a(x)$ by the monic $x^2 + x - 1$ instead of by $2x^2 + x - 1$ stays inside the integers:
$$x^4 + 2x^3 - x + 3 = (x^2 + x - 1)(x^2 + x) + 3.$$
Why the leading coefficient must be invertible
Without the hypothesis the theorem fails, and the simplest example is $x^2$ divided by $2x$ in $\mathbb{Z}[x]$. A remainder would have to be 0 or a constant, so $x^2 - r = 2x \cdot q(x)$ would have degree 2, forcing $q(x)$ to have degree 1 with some leading coefficient $c$. Comparing coefficients of $x^2$ gives $2c = 1$, which has no solution in $\mathbb{Z}$. In $\mathbb{Q}[x]$ the division is immediate: $x^2 = 2x \cdot \tfrac{1}{2}x + 0$.
The same thing happened in the opening division of $a(x)$ by $2x^2 + x - 1$. Over $\mathbb{Z}$ it fails at the first step; over $\mathbb{Q}$ it succeeds. Yet the rational answer needs much less than $\mathbb{Q}$, since its only denominators are 2, 4 and 8. Multiplying the opening identity by 8 clears them:
$$8\,a(x) = (2x^2 + x - 1)(4x^2 + 6x - 1) + (-x + 23),$$
an identity in $\mathbb{Z}[x]$ (script). For odd $n$, 2 and $8 = 2^3$ are units of $\mathbb{Z}_n$. Reading the identity modulo $n$, which congruence arithmetic allows, and multiplying by the inverse of 8 gives $a = bq + r$ in $\mathbb{Z}_n[x]$ with $q = 8^{-1}(4x^2 + 6x - 1)$ and $r = 8^{-1}(-x + 23)$, a remainder of degree 1. By uniqueness, that is the division in $\mathbb{Z}_n[x]$, whether $\mathbb{Z}_n$ is a field, like $\mathbb{Z}_7$, or not, like $\mathbb{Z}_{15}$. The division needs an inverse for the leading coefficient 2, and nothing else.
Long division is the proof as a procedure
The existence proof hides a procedure, as it did for integers, and here the procedure is fast. Starting from $r = a$, repeatedly subtract the multiple of $b(x)$ that cancels the leading term of $r$, until $r$ is 0 or has degree less than $\deg b$. The terms subtracted add up to the quotient. For the opening example, with $b(x) = 2x^2 + x - 1$:
| Step | Term of $q(x)$ | Subtract | Remainder so far |
|---|---|---|---|
| $x^4 + 2x^3 - x + 3$ | |||
| 1 | $\tfrac{1}{2}x^2$ | $x^4 + \tfrac{1}{2}x^3 - \tfrac{1}{2}x^2$ | $\tfrac{3}{2}x^3 + \tfrac{1}{2}x^2 - x + 3$ |
| 2 | $\tfrac{3}{4}x$ | $\tfrac{3}{2}x^3 + \tfrac{3}{4}x^2 - \tfrac{3}{4}x$ | $-\tfrac{1}{4}x^2 - \tfrac{1}{4}x + 3$ |
| 3 | $-\tfrac{1}{8}$ | $-\tfrac{1}{4}x^2 - \tfrac{1}{8}x + \tfrac{1}{8}$ | $-\tfrac{1}{8}x + \tfrac{23}{8}$ |
Each step lowers the degree of the remainder by at least one, so the procedure stops after at most $\deg a - \deg b + 1$ steps, three here. The count depends only on degrees, never on the size of the coefficients. This is the polynomial version of school long division handling one digit of the quotient at a time.
Check your understanding. Dividing the same $a(x)$ by the monic $x^2 + x - 1$ gave the quotient $x^2 + x$ and remainder 3. How many steps did long division take, and why not three?
Two. The first step leaves $x^3 + x^2 - x + 3$. The second subtracts $x(x^2 + x - 1)$ and leaves 3, so the degree falls from 3 straight to 0. The bound is reached only when each step lowers the degree by exactly one; a step that cancels more skips a quotient term, here the constant term of $x^2 + x$, which is 0.
Uniqueness says that no other quotient gives a remainder of degree less than 2. The script tries two nearby ones. With $q(x) + 1$ the "remainder" $a - b(q + 1)$ is $-2x^2 - \tfrac{9}{8}x + \tfrac{31}{8}$, of degree 2, and with $q(x) - x$ it is $2x^3 + x^2 - \tfrac{9}{8}x + \tfrac{23}{8}$, of degree 3. Changing the quotient by a nonzero $k(x)$ changes the remainder by $b(x)k(x)$, which has degree at least 2 and so cannot be absorbed.
Divisibility
With division in hand, the integer theory can be rebuilt, starting with divisibility. From here on, $F$ is a field.
Definition. Let $a(x), b(x) \in F[x]$ with $b(x) \neq 0$. Then $b(x)$ divides $a(x)$, written $b(x) \mid a(x)$, if $a(x) = b(x)k(x)$ for some $k(x) \in F[x]$. Two nonzero polynomials are associates if each is a nonzero constant multiple of the other, that is, $g(x) = c f(x)$ for some nonzero $c \in F$.
Since the units of $F[x]$ are the nonzero constants, associates are the polynomial version of $n$ and $-n$, which have the same divisors and multiples. A nonzero polynomial $f(x)$ with leading coefficient $a_n$ has exactly one monic associate, $a_n^{-1}f(x)$, because $cf(x)$ has leading coefficient $ca_n$, which equals 1 only for $c = a_n^{-1}$. Monic polynomials thus play the part of positive integers: one chosen representative from each family of associates.
For the polynomial $f(x) = x^4 + x^3 - x^2 - 2x - 2$, which is the running example of this unit,
$$f(x) = (x^2 + x + 1)(x^2 - 2) = (3x^2 + 3x + 3)\Big(\tfrac{1}{3}x^2 - \tfrac{2}{3}\Big),$$
so both $x^2 + x + 1$ and its associate $3x^2 + 3x + 3$ divide $f(x)$.
The laws of divisibility carry over from the integers with the same one-line proofs.
Lemma (laws of divisibility in $F[x]$). Let $a, b, c, u, v \in F[x]$.
- If $b \mid a$, then $cb \mid a$ for every nonzero constant $c$. Every nonzero constant divides every polynomial.
- If $b \mid a$ and $a \neq 0$, then $\deg b \le \deg a$.
- If $b \mid a$ and $a \mid c$, then $b \mid c$.
- If $b \mid a$ and $b \mid c$, then $b \mid (au + cv)$.
- If $a \mid b$ and $b \mid a$, then $a$ and $b$ are associates; if both are monic, $a = b$.
Proof. (1) If $a = bk$, then $a = (cb)(c^{-1}k)$. A nonzero constant $c$ divides $a$ because $a = c \cdot c^{-1}a$. (2) If $a = bk$ with $a \neq 0$, then $k \neq 0$, and the degree formula over the integral domain $F$ gives $\deg a = \deg b + \deg k \ge \deg b$. (3) If $a = bk$ and $c = al$, then $c = b(kl)$. (4) If $a = bk$ and $c = bl$, then $au + cv = b(ku + lv)$. (5) Write $b = ak$ and $a = bl$. Then $a = akl$, so $a(1 - kl) = 0$, and since $a \neq 0$ and $F[x]$ is an integral domain, $kl = 1$. So $k$ is a unit of $F[x]$, which is a nonzero constant, and $b = ka$. If both are monic, comparing leading coefficients gives $k = 1$. $\blacksquare$
These are the laws of divisibility for integers with three translations:
- absolute value becomes degree;
- the sign change $\pm 1$ becomes multiplication by a nonzero constant;
- "positive" becomes "monic".
Laws (1) and (2) are Hungerford's Theorem 4.7.
Greatest common divisors
For 1729 and 1001 the greatest common divisor was simply the largest number dividing both. For polynomials, "largest" can only mean largest degree.
Definition. Let $a(x), b(x) \in F[x]$, not both zero. A greatest common divisor of $a(x)$ and $b(x)$ is a monic polynomial of the largest possible degree that divides both. It is written $\gcd(a(x), b(x))$.
A monic common divisor always exists, because 1 divides everything, and by law (2) its degree is at most that of whichever of $a$ and $b$ is nonzero. So some monic common divisor has the largest possible degree. What the definition does not make obvious is that only one does: two different monic polynomials of the same degree might both divide $a$ and $b$. Degree compares sizes only roughly, and uniqueness has to be proved. The course text proves it through Bezout's identity (Hungerford, 2014, Theorem 4.8). The Euclidean algorithm gives a proof that also computes the answer.
Euclid's step
Lemma. If $a(x) = b(x)q(x) + r(x)$ in $F[x]$, then the common divisors of $a(x)$ and $b(x)$ are exactly the common divisors of $b(x)$ and $r(x)$.
Proof. A common divisor of $a$ and $b$ divides $r = a \cdot 1 + b \cdot(-q)$ by law (4). A common divisor of $b$ and $r$ divides $a = bq + r \cdot 1$ by the same law. $\blacksquare$
The proof is the integer proof word for word, because it uses only the law about linear combinations.
The Euclidean algorithm
Let $b(x) \neq 0$. Set $r_0 = a(x)$ and $r_1 = b(x)$, and as long as the latest remainder $r_i$ is not zero, divide the one before it by it:
$$r_{i-1} = r_i \, q_i + r_{i+1}, \qquad r_{i+1} = 0 \;\text{ or }\; \deg r_{i+1} < \deg r_i.$$
Stop at the first remainder that is zero, and call the last nonzero remainder $r_n$.
Here is the plan of the proof. Falling degrees make the algorithm stop, and Euclid's step keeps the common divisors unchanged all the way down to $r_n$.
Theorem (Euclidean algorithm). The procedure stops after at most $\deg b + 1$ divisions. The common divisors of $a(x)$ and $b(x)$ are exactly the divisors of $r_n$. Consequently:
- $a(x)$ and $b(x)$ have exactly one greatest common divisor, namely $r_n$ divided by its leading coefficient;
- every common divisor of $a(x)$ and $b(x)$ divides $\gcd(a(x), b(x))$.
Proof. The nonzero remainders after $r_1$ have strictly decreasing degrees, $\deg b > \deg r_2 > \deg r_3 > \cdots \ge 0$, so there are at most $\deg b$ of them, and the zero remainder appears after at most $\deg b + 1$ divisions. By the lemma, applied once for each division, the common divisors of $a$ and $b$ are the common divisors of $r_0$ and $r_1$, of $r_1$ and $r_2$, and so on down to $r_n$ and $0$. Every nonzero polynomial divides 0, so the common divisors of $r_n$ and 0 are the divisors of $r_n$.
(1) A divisor of $r_n$ has degree at most $\deg r_n$, by law (2), and the monic associate $d = r_n / \mathrm{lc}(r_n)$ is a divisor of that degree, where $\mathrm{lc}$ denotes the leading coefficient. So the largest degree of a common divisor is $\deg r_n$. If $e$ is any monic common divisor of that degree, then $r_n = ek$ with $\deg k = 0$, so $k$ is a nonzero constant and $e$ is an associate of $r_n$. A family of associates contains exactly one monic member, so $e = d$. (2) Every common divisor divides $r_n$, hence divides its associate $d$, by law (1). $\blacksquare$
Corollary. A monic polynomial $d(x)$ is the greatest common divisor of $a(x)$ and $b(x)$ if and only if $d(x)$ divides both and every common divisor of $a(x)$ and $b(x)$ divides $d(x)$.
Proof. The greatest common divisor has both properties, by the theorem. Conversely, if $d$ has them, then $d \mid \gcd(a, b)$ because $d$ is a common divisor, and $\gcd(a, b) \mid d$ because the gcd is a common divisor. By law (5), the two monic polynomials are equal. $\blacksquare$
This is Hungerford's Corollary 4.9, and the integer version is the corollary there that "greatest" can be read as "divisible by every common divisor". For polynomials that reading is the essential one, since degrees cannot rank two common divisors of the same degree.
The running pair
Take the running example together with a second quartic,
$$f(x) = x^4 + x^3 - x^2 - 2x - 2, \qquad g(x) = x^4 - 2x^2 - 3x - 2,$$
in $\mathbb{Q}[x]$. For 1729 and 1001 the algorithm took five divisions. Here it takes three:
$$\begin{aligned} x^4 + x^3 - x^2 - 2x - 2 &= (x^4 - 2x^2 - 3x - 2) \cdot 1 + (x^3 + x^2 + x), \\ x^4 - 2x^2 - 3x - 2 &= (x^3 + x^2 + x)(x - 1) + (-2x^2 - 2x - 2), \\ x^3 + x^2 + x &= (-2x^2 - 2x - 2)\Big({-\tfrac{1}{2}}x\Big) + 0. \end{aligned}$$
The last nonzero remainder is $-2x^2 - 2x - 2$, which is not monic. Dividing by its leading coefficient $-2$ gives
$$\gcd(f, g) = x^2 + x + 1.$$
This step has no counterpart for integers, where the last nonzero remainder, 91 for the running pair, is positive and is the answer as it stands. Here the last nonzero remainder can be any nonzero constant multiple of the gcd, depending on the polynomials divided. Normalizing to a monic polynomial picks the one representative. The fraction $-\tfrac{1}{2}$ in the last quotient is where the field is used.
The answer can be checked against factorizations, as $91 = 7 \cdot 13$ was checked against $1729 = 7 \cdot 13 \cdot 19$ and $1001 = 7 \cdot 11 \cdot 13$. Here $f(x) = (x^2 - 2)(x^2 + x + 1)$ and $g(x) = (x - 2)(x + 1)(x^2 + x + 1)$, and the shared factor is $x^2 + x + 1$. The article on Irreducible Polynomials and Roots proves that factorizations like these are unique, which is what makes the check legitimate. The Euclidean algorithm needs no factorization at all, and for large polynomials that is its advantage, exactly as for large integers.
The bound of $\deg b + 1$ divisions is often reached, because each division usually lowers the degree by exactly one. Among all $81 \times 27 = 2187$ pairs of a monic quartic and a monic cubic in $\mathbb{Z}_3[x]$, the script finds that 648 need the full four divisions, 972 need three, 486 need two and 81 need one. There is no polynomial counterpart of Lamé's theorem to prove: the degree argument already gives a bound in terms of the size of the input, since the degree is the length of the polynomial.
Check your understanding. The first division gave the remainder $f - g = x^3 + x^2 + x$, which both $x$ and $x^2 + x + 1$ divide. Does law (4) then say that $x$ divides $f$?
It does not. Law (4) runs in one direction only, just as 10 divides $1729 + 1001$ without dividing either. Here $x$ divides a polynomial exactly when its constant term is 0, and the constant term of $f$ is $-2$. Euclid's step guarantees only that a common divisor of $f$ and $g$, such as $x^2 + x + 1$, divides every remainder.
Bezout's identity
For integers, reading the divisions backwards gave $91 = 1729 \cdot (-4) + 1001 \cdot 7$. Does the same work for polynomials? It does, with fractions. The first division gives $r_2 = f - g$. The second gives
$$r_3 = g - (x - 1) r_2 = g - (x - 1)(f - g) = -(x - 1) f + x\, g.$$
Dividing by $-2$:
$$x^2 + x + 1 = \frac{x - 1}{2}\, f(x) - \frac{x}{2}\, g(x).$$
Theorem (Bezout's identity in $F[x]$). Let $a(x), b(x) \in F[x]$, not both zero, and $d(x) = \gcd(a(x), b(x))$. There exist $u(x), v(x) \in F[x]$ such that
$$d(x) = a(x)u(x) + b(x)v(x).$$
The idea of the proof is that each division forms the next remainder as a combination of the previous two, so every remainder is a combination of $a$ and $b$.
Proof. If $b = 0$, then $a \neq 0$, the common divisors of $a$ and 0 are the divisors of $a$, and $d = a \cdot \mathrm{lc}(a)^{-1} + b \cdot 0$. Otherwise run the Euclidean algorithm. We show by induction that each remainder is a combination $r_i = a s_i + b t_i$. For $r_0 = a$ and $r_1 = b$, take $(s_0, t_0) = (1, 0)$ and $(s_1, t_1) = (0, 1)$. If the claim holds for $r_{i-1}$ and $r_i$, then
$$r_{i+1} = r_{i-1} - q_i r_i = a\,(s_{i-1} - q_i s_i) + b\,(t_{i-1} - q_i t_i).$$
So it holds for every remainder, in particular for $r_n$, and multiplying by $\mathrm{lc}(r_n)^{-1}$ gives $d = a \cdot \mathrm{lc}(r_n)^{-1}s_n + b \cdot \mathrm{lc}(r_n)^{-1}t_n$. $\blacksquare$
The recurrences give the extended Euclidean algorithm, which computes the coefficients alongside the remainders. Each row satisfies $r_i = f\,s_i + g\,t_i$, and row $i + 1$ is row $i - 1$ minus $q_i$ times row $i$, in all three columns:
| $i$ | $r_i$ | $s_i$ | $t_i$ | $q_i$ |
|---|---|---|---|---|
| 0 | $x^4 + x^3 - x^2 - 2x - 2$ | $1$ | $0$ | |
| 1 | $x^4 - 2x^2 - 3x - 2$ | $0$ | $1$ | $1$ |
| 2 | $x^3 + x^2 + x$ | $1$ | $-1$ | $x - 1$ |
| 3 | $-2x^2 - 2x - 2$ | $-x + 1$ | $x$ | $-\tfrac{1}{2}x$ |
| 4 | $0$ | $-\tfrac{1}{2}x^2 + \tfrac{1}{2}x + 1$ | $\tfrac{1}{2}x^2 - 1$ |
Row 3, divided by $-2$, is the identity found above. Row 4 says $f s_4 + g t_4 = 0$, and its entries are $-\tfrac{1}{2}$ times $g/d = x^2 - x - 2$ and $\tfrac{1}{2}$ times $f/d = x^2 - 2$. As with integers, the coefficients are not unique: adding $(g/d)\,k$ to $u$ and subtracting $(f/d)\,k$ from $v$, for any polynomial $k$, leaves $fu + gv$ unchanged. With $k = 1$ this gives
$$x^2 + x + 1 = \Big(x^2 - \tfrac{1}{2}x - \tfrac{5}{2}\Big) f(x) + \Big({-x^2} - \tfrac{1}{2}x + 2\Big) g(x),$$
which the script confirms. Bezout's identity for polynomials is part of Hungerford's Theorem 4.8 and is Judson's Proposition 17.2.5. Both prove it by taking a combination of smallest degree, as the course text did for integers, and then derive the gcd from it.
Check your understanding. Both Bezout pairs above have the denominator 2. Is there a pair $u(x), v(x)$ with integer coefficients that gives $x^2 + x + 1 = f u + g v$?
There is not, and evaluation proves it without searching. Substitute $x = 2$, where $g(2) = 0$. Any such pair satisfies $d(2) = f(2)\,u(2)$, that is, $7 = 14\,u(2)$, so $u(2) = \tfrac{1}{2}$ for every choice of $u$. A polynomial with integer coefficients takes an integer value at 2, so the fractions are forced.
Relatively prime polynomials
For integers, the most useful consequence of Bezout's identity was cancellation, and so it is here. Polynomials whose greatest common divisor is 1 are relatively prime.
Corollary. $a(x)$ and $b(x)$ are relatively prime if and only if $a(x)u(x) + b(x)v(x) = 1$ for some $u(x), v(x) \in F[x]$.
Proof. If the gcd is 1, Bezout's identity gives the combination. Conversely, any common divisor divides the combination 1 by law (4), so it has degree 0; the only monic polynomial of degree 0 is 1. $\blacksquare$
For example, $x^2 - 2$ and $g(x)$ are relatively prime, and the extended algorithm gives
$$(x^2 - 2)\Big(\tfrac{3}{14}x^3 - \tfrac{1}{7}x^2 - \tfrac{9}{14}\Big) + g(x)\Big({-\tfrac{3}{14}}x + \tfrac{1}{7}\Big) = 1.$$
The idea of cancellation is to multiply the combination $1 = au + bv$ by $c$. That writes $c$ as a combination of $a$ and $bc$, two polynomials that $a$ divides.
Theorem (cancellation). Let $a(x), b(x), c(x) \in F[x]$. If $a(x) \mid b(x)c(x)$ and $a(x)$ and $b(x)$ are relatively prime, then $a(x) \mid c(x)$.
Proof. Write $1 = au + bv$ and multiply by $c$: $c = a(cu) + (bc)v$. The polynomial $a$ divides $a(cu)$ and divides $bc$ by hypothesis, so it divides $c$ by law (4). $\blacksquare$
This is Hungerford's Theorem 4.10, and its proof is the integer proof with polynomials in every place. Coprimality is needed. The running example $f$ divides $g(x)(x^2 - 2) = x^6 - 4x^4 - 3x^3 + 2x^2 + 6x + 4$, with quotient $x^2 - x - 2$, but $f$ divides neither $g(x)$ nor $x^2 - 2$. The factors of $f$, namely $x^2 + x + 1$ and $x^2 - 2$, are shared out between the two, as the factors 2 and 5 of 10 were shared between 4 and 15 in $10 \mid 4 \cdot 15$. With $a(x)$ irreducible, the theorem becomes Euclid's lemma for polynomials, the key to unique factorization.
Check your understanding. The combination equal to 1 found above shows that $x^2 - 2$ and $g(x)$ are relatively prime. Can $x^2 - 2$ divide $g(x)^2$? Compare the integer question of whether 19 can divide $1001^2$.
It cannot. If $x^2 - 2$ divided $g(x) \cdot g(x)$, cancellation, with $b = c = g$, would give $x^2 - 2 \mid g(x)$. Then $x^2 - 2$ would be a common divisor of itself and $g$ of degree 2, while their gcd is 1. The script confirms that $g(x)^2$ leaves the remainder $12x + 22$ on division by $x^2 - 2$. In the same way $\gcd(19, 1001) = 1$ keeps 19 from dividing $1001^2$.
The gcd and the choice of field
The polynomials $f$ and $g$ have rational coefficients, but they are also polynomials over $\mathbb{R}$ and over $\mathbb{C}$. Over $\mathbb{C}$ the common factor $x^2 + x + 1$ splits into two linear factors, and over $\mathbb{R}$ the factor $x^2 - 2$ of $f$ splits as $(x - \sqrt{2})(x + \sqrt{2})$. Does the greatest common divisor change? It does not. Here is the idea in one sentence: the Euclidean algorithm over $\mathbb{Q}$ never leaves $\mathbb{Q}$, and by uniqueness its divisions are also the divisions the algorithm would make over the larger field.
Proposition. Let $F \subseteq K$ be fields, and let $a(x), b(x) \in F[x]$, not both zero. The greatest common divisor of $a(x)$ and $b(x)$ in $K[x]$ equals their greatest common divisor in $F[x]$. In particular it has coefficients in $F$.
Proof. If $b = 0$, both gcds are the monic associate of $a$. Otherwise run the Euclidean algorithm in $F[x]$. Each of its division equations $r_{i-1} = r_i q_i + r_{i+1}$ is also an equation in $K[x]$, with a remainder of smaller degree than the divisor. By the uniqueness half of the division algorithm in $K[x]$, these are the divisions that the Euclidean algorithm performs in $K[x]$. So the algorithm in $K[x]$ produces the same remainders and the same last nonzero remainder, and the two gcds are its monic associate. $\blacksquare$
So $\gcd(f, g) = x^2 + x + 1$ over $\mathbb{R}$ and over $\mathbb{C}$ as well. Over $\mathbb{C}$ it is $(x - \omega)(x - \bar\omega)$, with $\omega = -\tfrac{1}{2} + \tfrac{\sqrt{3}}{2}i$, and over $\mathbb{R}$ the new factors $x \mp \sqrt{2}$ of $f$ do not divide $g$, since $g(\pm\sqrt{2}) \neq 0$ (the factor theorem makes this a valid test). Enlarging the field can split the common factor, but it cannot create a new one.
Reducing the coefficients modulo a prime is a different operation, because $\mathbb{Z}_p$ does not contain $\mathbb{Q}$, and it can create common factors. Modulo 2, $f$ becomes $x^4 + x^3 + x^2 = x^2(x^2 + x + 1)$ and $g$ becomes $x^4 + x = x(x + 1)(x^2 + x + 1)$, so the gcd in $\mathbb{Z}_2[x]$ is $x^3 + x^2 + x$, of degree 3. Modulo 3, 5, 7, 11 and 13 the script finds the gcd $x^2 + x + 1$ again. The divisions over $\mathbb{Q}$ involved the denominator 2, which has no meaning modulo 2, so the computation over $\mathbb{Q}$ says nothing about $\mathbb{Z}_2$.
Where it leads
- Irreducible polynomials, the primes of $F[x]$, satisfy Euclid's lemma by the cancellation theorem, and every polynomial factors into them uniquely (Irreducible Polynomials and Roots). The remainder theorem there is the division algorithm with divisor $x - c$.
- The remainders on division by a fixed polynomial $p(x)$ are the natural representatives of congruence classes modulo $p(x)$, and Bezout's identity computes inverses among them, as it did in the integers modulo $n$. This is how arithmetic is done in the fields built from irreducible polynomials.
- A ring with a division algorithm measured by a size function is a Euclidean domain, and an argument like the one in this article shows that in such a ring every ideal is generated by one element: $F[x]$ is a principal ideal domain, like $\mathbb{Z}$.
What we have learned
Division with a remainder of smaller degree works whenever the divisor's leading coefficient is invertible, so over a field it always works, with a unique quotient and remainder. The integer theory then returns almost word for word. The Euclidean algorithm finds $\gcd(f, g) = x^2 + x + 1$ in three divisions, once the last remainder is made monic. Run backwards, it gives $x^2 + x + 1 = \tfrac{x - 1}{2} f - \tfrac{x}{2} g$, and Bezout's identity gives cancellation. The gcd stays the same over any larger field but can change modulo a prime.
For integers, cancellation by a prime became Euclid's lemma, and Euclid's lemma gave unique factorization. What are the "primes" of $F[x]$, and is factorization into them unique? That is Irreducible Polynomials and Roots.
References
- Hungerford, T. W. (2014). Abstract Algebra: An Introduction (3rd ed.), §4.1 and §4.2. Brooks/Cole, Cengage Learning. The course text: the division algorithm in $F[x]$ (Theorem 4.6), divisors and degrees (Theorem 4.7), the greatest common divisor as a linear combination (Theorem 4.8), its characterization by divisibility (Corollary 4.9), and cancellation (Theorem 4.10). record · 44 pages
- Judson, T. W. (2026). Abstract Algebra: Theory and Applications (annual edition, August 2026), §17.2: the division algorithm (Theorem 17.2.1) and the greatest common divisor as a combination (Proposition 17.2.5). Free online at judsonbooks.org. record · 44 pages