6.2 Ideals and Greatest Common Divisors

Division with remainder is now available over every field. This section uses it to answer a question about two polynomials $f$ and $g$ : what do all the combinations $af + bg$ , with polynomial coefficients $a$ and $b$ , look like? The answer is that they are exactly the multiples of one polynomial, and that polynomial is the greatest common divisor of $f$ and $g$ . Along the way we meet ideals, the subsets of $F[x]$ adapted to multiplication, and we prove that each of them is generated by a single polynomial. The Euclidean algorithm then computes the greatest common divisor and the coefficients $a, b$ by repeated division. Throughout, $F$ is a field.

6.2.1. All the combinations of two polynomials

Take $f = x^2 - 1$ and $g = x^2 + x - 2$ in $\mathbb{Q}[x]$ , and look at the set $\{ af + bg : a, b \in \mathbb{Q}[x] \}$ of all their combinations with polynomial coefficients. It contains $f$ (take $a = 1, b = 0$ ), $g$ , and $g - f = x - 1$ .

Since $f = (x - 1)(x + 1)$ and $g = (x - 1)(x + 2)$ , every combination is $af + bg = (x - 1)\bigl( a(x + 1) + b(x + 2) \bigr),$ a multiple of $x - 1$ . Conversely, every multiple $h(x - 1)$ is a combination, namely $(-h)f + hg$ . So the set of combinations is exactly the set of multiples of $x - 1$ . Its non-zero members of smallest degree are the non-zero scalar multiples of $x - 1$ . By Proposition 6.1.2 (c), no non-zero constant is a multiple of $x - 1$ , so there is nothing of degree $0$ .

Two features of this set will carry the whole section. It is closed under addition, and it absorbs multiplication by any polynomial: if $af + bg$ is in the set, so is $h(af + bg) = (ha)f + (hb)g$ . Sets with these two features appear everywhere, so they get a name.

6.2.2. Ideals

In Chapter 1 we studied $F[x]$ as a vector space and its subspaces: subsets closed under addition and under multiplication by scalars. But $F[x]$ also has a multiplication of its own. The subsets that respect it are closed under multiplication by polynomials. Three recurring examples share this feature:

the multiples of a fixed polynomial $p$ ;
the combinations $af + bg$ of two fixed polynomials;
the polynomials that vanish at a fixed point $c$ : if $f(c) = 0$ , then $(hf)(c) = h(c) \cdot 0 = 0$ for every $h$ .

An ideal is a set of polynomials that is closed under addition and swallows multiplication by anything.

Definition 6.2.1 (Ideal of

F\lbrack x\rbrack

)

Let $F$ be a field. A subset $I \subseteq F[x]$ is an ideal of $F[x]$ if

(I1) $I$ is non-empty;
(I2) $f + g \in I$ for all $f, g \in I$ ;
(I3) $hf \in I$ for all $f \in I$ and every $h \in F[x]$ .

For $f_1, \dots, f_k \in F[x]$ , write $\langle f_1, \dots, f_k \rangle \mathrel{:=} \{ a_1 f_1 + \dots + a_k f_k : a_1, \dots, a_k \in F[x] \} .$ In particular $\langle p \rangle = \{ hp : h \in F[x] \}$ is the set of all multiples of $p$ .

In words: (I1) rules out the empty set. (I2) says sums stay inside. (I3) is the new clause: a member of $I$ multiplied by any polynomial, not just by a constant, is still a member. Taking $h = 0$ in (I3) shows $0 \in I$ , and taking $h = -1$ shows $-f \in I$ . Taking $h = c$ constant shows $I$ is closed under scalar multiplication, so every ideal is a subspace of $F[x]$ by Theorem 1.2.1.

The angle brackets here have nothing to do with the inner products of later chapters: $\langle f, g \rangle$ is a set of polynomials, not a number.

Well-definedness. We have named the set $\langle f_1, \dots, f_k \rangle$ , and must check that it is an ideal. It is in fact the smallest ideal containing $f_1, \dots, f_k$ .

Proposition 6.2.1 (The Ideal Generated by Finitely Many Polynomials)

Let $F$ be a field and $f_1, \dots, f_k \in F[x]$ , with $k \ge 1$ . Then $\langle f_1, \dots, f_k \rangle$ is an ideal of $F[x]$ containing $f_1, \dots, f_k$ . Moreover, every ideal $J$ of $F[x]$ with $f_1, \dots, f_k \in J$ satisfies $\langle f_1, \dots, f_k \rangle \subseteq J$ .

Proof. Let $I = \langle f_1, \dots, f_k \rangle$ . Taking $a_i = 1$ and $a_j = 0$ for $j \neq i$ shows $f_i \in I$ ; in particular (I1) holds. For (I2), $\sum a_i f_i + \sum b_i f_i = \sum (a_i + b_i) f_i \in I$ . For (I3), $h \sum a_i f_i = \sum (h a_i) f_i \in I$ , using Theorem 0.8.1 in both cases. So $I$ is an ideal.

Now let $J$ be an ideal containing every $f_i$ . By (I3) for $J$ , each $a_i f_i \in J$ , and by (I2) applied $k - 1$ times, $a_1 f_1 + \dots + a_k f_k \in J$ . Hence $I \subseteq J$ . This proves the proposition.

The ideal $\langle f_1, \dots, f_k \rangle$ is the ideal generated by $f_1, \dots, f_k$ . An ideal of the form $\langle p \rangle$ , generated by one polynomial, is called principal.

Example (First Ideals)

Check each of the following against Definition 6.2.1.

(a) $\{0\}$ and $F[x]$ ; and any ideal containing a non-zero constant.
(b) $I_c = \{ f \in F[x] : f(c) = 0 \}$ for a fixed $c \in F$ .
(c) For $\mathbf{A} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \in M_2(F)$ , the set $\{ p \in F[x] : p(\mathbf{A}) = 0 \}$ .

Solution.

(a) $\{0\} = \langle 0 \rangle$ and $F[x] = \langle 1 \rangle$ are ideals by Proposition 6.2.1. They are the degenerate cases, and the second one is the one to recognize: if an ideal $I$ contains a non-zero constant $c$ , then $1 = c^{-1} c \in I$ by (I3), and then $h = h \cdot 1 \in I$ for every $h$ , so $I = F[x]$ . An ideal that contains a non-zero constant is everything.
(b) $0 \in I_c$ . If $f(c) = g(c) = 0$ , then $(f + g)(c) = 0$ and $(hf)(c) = h(c) f(c) = 0$ for every $h \in F[x]$ , by Theorem 0.8.5. So $I_c$ is an ideal. By Theorem 6.1.3 (b), $f(c) = 0$ exactly when $x - c \mid f$ , so $I_c = \langle x - c \rangle$ .
(c) Call the set $I$ . The zero polynomial is in $I$ . If $p(\mathbf{A}) = q(\mathbf{A}) = 0$ , then by Theorem 0.9.9, $(p + q)(\mathbf{A}) = p(\mathbf{A}) + q(\mathbf{A}) = 0$ and $(hp)(\mathbf{A}) = h(\mathbf{A})\,p(\mathbf{A}) = h(\mathbf{A}) \cdot 0 = 0$ for every $h$ . So $I$ is an ideal. It contains $x^2$ , since $\mathbf{A}^2 = 0$ . It contains no non-zero polynomial of degree at most $1$ : $(a + bx)(\mathbf{A}) = \begin{pmatrix} a & b \\ 0 & a \end{pmatrix} = 0$ forces $a = b = 0$ . The same argument works for any linear operator $T$ in place of $\mathbf{A}$ , with Theorem 2.4.3. In Chapter 9 the ideal of all polynomials killing an operator is where the minimal polynomial comes from.

Now the non-example, by a minimal change. Take $F[x]_{\le n}$ for some $n \in \mathbb{N}$ . It is non-empty, closed under addition, and closed under multiplication by constants: it is a subspace of $F[x]$ (Example (Polynomials of Bounded Degree)). But it fails (I3): $x^n \in F[x]_{\le n}$ and $x \in F[x]$ , while $x \cdot x^n = x^{n+1} \notin F[x]_{\le n}$ . The exact clause that fails is “for every $h \in F[x]$ ”.

Why insist on every $h$ , and not just constants? Because the main theorem below divides a member $f$ of $I$ by another member $d$ and needs the remainder $f - qd$ to lie in $I$ again. The quotient $q$ is an arbitrary polynomial, so we need $qd \in I$ . With only closure under scalars, the argument breaks, and indeed $F[x]_{\le n}$ is not the set of multiples of any single polynomial. The name “ideal” is historical and says nothing about the definition.

Warning. Do not confuse $\langle f, g \rangle$ with $\operatorname{span}(f, g)$ . The span uses scalar coefficients, the ideal uses polynomial coefficients. For example, $\operatorname{span}(x) = \{ cx : c \in F \}$ is a line in $F[x]$ , while $\langle x \rangle$ contains $x^2, x^3, \dots$ and is infinite-dimensional. Every ideal is a subspace, but most subspaces, such as $F[x]_{\le n}$ or $\operatorname{span}(x)$ , are not ideals.

Quick check. Is $J = \{ f \in \mathbb{R}[x] : f(1) = 0 \text{ or } f(2) = 0 \}$ an ideal of $\mathbb{R}[x]$ ?

Solution. No. $J$ is non-empty and satisfies (I3), since $(hf)(c) = h(c)f(c)$ . But it fails (I2): $x - 1 \in J$ and $x - 2 \in J$ , while their sum $2x - 3$ takes the values $-1$ at $1$ and $1$ at $2$ , so $2x - 3 \notin J$ . The set with “and” in place of “or” is an ideal.

6.2.3. Every ideal is generated by one polynomial

The payoff of the definition is that ideals of $F[x]$ are very simple: each one is the set of multiples of a single polynomial. The proof is the argument of the opening example, made general. We have met it before for integers, in Lemma 0.7.2, where the smallest positive combination $ax + ny$ turned out to divide $a$ and $n$ .

Theorem 6.2.2 (Every Ideal of

F\lbrack x\rbrack

Is Principal)

Let $F$ be a field and $I$ an ideal of $F[x]$ . If $I \neq \{0\}$ , there is exactly one monic polynomial $d$ with $I = \langle d \rangle$ . Moreover, $d$ is the unique monic polynomial of least degree in $I$ .

Idea. Pick a non-zero $d \in I$ of smallest degree, made monic. Every multiple of $d$ is in $I$ by (I3). For the other inclusion, divide any $f \in I$ by $d$ : the remainder $r = f - qd$ lies in $I$ and has degree smaller than $\deg d$ . Minimality leaves only one option, $r = 0$ . Uniqueness is mutual divisibility of monic polynomials.

Proof. Suppose $I \neq \{0\}$ . The degrees of the non-zero elements of $I$ form a non-empty set of natural numbers, so by Theorem 0.2.11 it has a least element $m$ . Choose $g \in I$ with $\deg g = m$ , and let $c$ be its leading coefficient. Put $d = c^{-1} g$ . Then $d \in I$ by (I3), and $d$ is monic of degree $m$ .

$(\supseteq)$ For every $h \in F[x]$ , $hd \in I$ by (I3). Hence $\langle d \rangle \subseteq I$ .

$(\subseteq)$ Let $f \in I$ . By Theorem 6.1.1, $f = qd + r$ with $\deg r < m$ . By (I3), $-qd \in I$ , and by (I2), $r = f + (-qd) \in I$ . If $r \neq 0$ , then $r$ is a non-zero element of $I$ of degree less than $m$ , contradicting the choice of $m$ . Hence $r = 0$ , so $f = qd \in \langle d \rangle$ .

Therefore $I = \langle d \rangle$ . For uniqueness, let $d'$ be monic with $I = \langle d' \rangle$ . Then $d \in \langle d' \rangle$ and $d' \in \langle d \rangle$ , so $d' \mid d$ and $d \mid d'$ . Both are monic, so $d = d'$ by Proposition 6.1.2 (d).

Finally, let $e \in I$ be monic of least degree $m$ . Then $d \mid e$ , so $e = ud$ with $\deg u = 0$ by Theorem 0.8.3, and comparing leading coefficients gives $u = 1$ . Hence $e = d$ . This proves the theorem.

For $I = \{0\}$ the only generator is $0$ , since $\langle p \rangle$ contains $p$ . So every ideal of $F[x]$ is principal, with a canonical generator: $0$ for the zero ideal, and the monic polynomial of least degree otherwise. The named move is: the smallest-degree element of an ideal generates it. In Example (First Ideals) (c), the ideal contains $x^2$ and nothing non-zero of smaller degree, so it equals $\langle x^2 \rangle$ .

The theorem also turns divisibility into containment. For $p, q \in F[x]$ , $\langle p \rangle \subseteq \langle q \rangle \quad \Longleftrightarrow \quad q \mid p ,$ because $\langle p \rangle \subseteq \langle q \rangle$ holds exactly when $p \in \langle q \rangle$ , by Proposition 6.2.1. The bigger the ideal, the smaller the generator.

Quick check. Find the monic generator of $\langle x^2 - 1, \; x^3 - 1 \rangle \subseteq \mathbb{Q}[x]$ by finding an element of small degree in it.

Solution. The ideal contains $(x^3 - 1) - x(x^2 - 1) = x - 1$ . Both generators are multiples of $x - 1$ , since $x^2 - 1 = (x - 1)(x + 1)$ and $x^3 - 1 = (x - 1)(x^2 + x + 1)$ , so every combination is a multiple of $x - 1$ by Proposition 6.1.2 (b). A non-zero constant is not a multiple of $x - 1$ , so $x - 1$ has least degree in the ideal. By Theorem 6.2.2, the ideal is $\langle x - 1 \rangle$ .

6.2.4. The greatest common divisor

Apply Theorem 6.2.2 to the ideal $\langle f, g \rangle$ of all combinations. It has a canonical generator, and in the opening example that generator, $x - 1$ , was a common divisor of $f$ and $g$ . A naive attempt to define “the greatest common divisor” as “a common divisor of largest degree” runs into a problem at once: $x - 1$ , $2x - 2$ and $-\tfrac13 x + \tfrac13$ are all common divisors of $x^2 - 1$ and $x^2 + x - 2$ of the largest possible degree. Degree cannot tell associates apart, and it also does not say how the common divisors relate to each other. The generator of the ideal fixes both problems.

The gcd of $f$ and $g$ is the monic polynomial whose multiples are exactly the combinations of $f$ and $g$ .

Definition 6.2.2 (Greatest Common Divisor)

Let $F$ be a field and $f, g \in F[x]$ . If $f$ and $g$ are not both zero, the greatest common divisor $\gcd(f, g)$ is the unique monic polynomial $d \in F[x]$ with $\langle f, g \rangle = \langle d \rangle .$ We set $\gcd(0, 0) = 0$ .

In words: form the ideal of all combinations $af + bg$ with $a, b \in F[x]$ ; it is generated by one polynomial; take the monic one. The definition refers to $F[x]$ twice, in the coefficients $a, b$ and in the generator $d$ , so at first sight the gcd depends on the field. We show below that it does not change when the field is enlarged.

Well-definedness. By Proposition 6.2.1, $\langle f, g \rangle$ is an ideal. If $f$ and $g$ are not both zero, it contains a non-zero element, so by Theorem 6.2.2 there is exactly one monic $d$ with $\langle f, g \rangle = \langle d \rangle$ . The convention $\gcd(0, 0) = 0$ keeps the equation $\langle f, g \rangle = \langle \gcd(f, g) \rangle$ true in the remaining case. The definition is symmetric: $\gcd(f, g) = \gcd(g, f)$ .

Example (First Greatest Common Divisors)

(a) Let $f \neq 0$ have leading coefficient $a$ . Find $\gcd(f, 0)$ and $\gcd(f, c)$ for a non-zero constant $c$ .
(b) Find $\gcd(x^2 - 1, x^2 + x - 2)$ in $\mathbb{Q}[x]$ .
(c) Find $\gcd(x^2 + 1, x + 1)$ in $\mathbb{Q}[x]$ and in $\mathbb{F}_2[x]$ .

Solution.

(a) $\langle f, 0 \rangle = \{ af : a \in F[x] \} = \langle f \rangle = \langle a^{-1} f \rangle$ , and $a^{-1} f$ is monic, so $\gcd(f, 0) = a^{-1} f$ , the monic associate of $f$ . This degenerate case shows why the gcd must be made monic: $f$ itself generates the ideal too, but is not the canonical choice. Next, $\langle f, c \rangle$ contains the non-zero constant $c$ , so it is $F[x] = \langle 1 \rangle$ by Example (First Ideals) (a). Hence $\gcd(f, c) = 1$ .
(b) The opening example showed $\langle x^2 - 1, x^2 + x - 2 \rangle = \langle x - 1 \rangle$ , and $x - 1$ is monic. So the gcd is $x - 1$ .
(c) In $\mathbb{Q}[x]$ : dividing, $x^2 + 1 = (x - 1)(x + 1) + 2$ . So $2 = (x^2 + 1) - (x - 1)(x + 1)$ lies in the ideal, which is therefore $\mathbb{Q}[x]$ by Example (First Ideals) (a). Hence $\gcd = 1$ . In $\mathbb{F}_2[x]$ : $x^2 + 1 = (x + 1)^2$ , so $x^2 + 1 \in \langle x + 1 \rangle$ , and $\langle x^2 + 1, x + 1 \rangle = \langle x + 1 \rangle$ by Proposition 6.2.1. Hence $\gcd = x + 1$ . The symbols are the same, but $\mathbb{F}_2$ is not a field containing $\mathbb{Q}$ , so the two answers need not agree.

For a non-example by minimal change, keep (b) but replace $x - 1$ by the associate $3x - 3$ . It is still a common divisor of largest degree and still generates the ideal, but it is not $\gcd(x^2 - 1, x^2 + x - 2)$ : the clause “monic” fails. Or keep “monic” but lower the degree: $1$ is a monic common divisor, and it does not generate the ideal, since $1 \notin \langle x - 1 \rangle$ .

Why define the gcd through the ideal, rather than as “the largest common divisor”? Because the ideal definition delivers three things at once: existence and uniqueness (from Theorem 6.2.2), the fact that the gcd is a combination of $f$ and $g$ , and the fact that it is “greatest” in the strongest sense, namely that every common divisor divides it. Here is the last point.

Theorem 6.2.3 (Characterization of the gcd)

Let $F$ be a field, $f, g \in F[x]$ , and $d = \gcd(f, g)$ .

(a) $d \mid f$ and $d \mid g$ .
(b) If $h \in F[x]$ satisfies $h \mid f$ and $h \mid g$ , then $h \mid d$ .
(c) If $f, g$ are not both zero, then $d$ is the only monic polynomial with properties (a) and (b).

Proof.

(a) $f = 1 \cdot f + 0 \cdot g \in \langle f, g \rangle = \langle d \rangle$ , so $d \mid f$ . Similarly $d \mid g$ .
(b) Since $d \in \langle d \rangle = \langle f, g \rangle$ , there are $a, b \in F[x]$ with $d = af + bg$ . If $h \mid f$ and $h \mid g$ , then $h \mid af + bg = d$ by Proposition 6.1.2 (b).
(c) Let $e$ be monic with properties (a) and (b). Since $d$ is a common divisor of $f$ and $g$ , property (b) for $e$ gives $d \mid e$ . Since $e$ is a common divisor, property (b) for $d$ gives $e \mid d$ . Both are monic ( $e$ by assumption, and $d$ by Definition 6.2.2, since $f, g$ are not both zero), so $d = e$ by Proposition 6.1.2 (d). This proves the theorem.

So $\gcd(f, g)$ is a common divisor that every common divisor divides. If $f, g$ are not both zero, then $d \neq 0$ , and by Proposition 6.1.2 (c) every common divisor has degree at most $\deg d$ ; “greatest” is true for degrees as well. The proof of (b) used one fact that deserves its own statement, because it is the most useful property of the gcd.

Corollary 6.2.4 (Bézout’s Identity for Polynomials)

Let $F$ be a field and $f, g \in F[x]$ . Then there exist $a, b \in F[x]$ with $\gcd(f, g) = af + bg .$

Proof. By Definition 6.2.2, $\gcd(f, g) \in \langle \gcd(f, g) \rangle = \langle f, g \rangle$ , and the elements of $\langle f, g \rangle$ are exactly the combinations $af + bg$ .

The coefficients are not unique: if $d = af + bg$ , then also $d = (a + g)f + (b - f)g$ . Bézout’s identity is the polynomial version of Lemma 0.7.2, and it will be the tool behind the Chinese Remainder Theorem and the splitting of kernels later in this chapter.

6.2.5. The Euclidean algorithm

The definition tells us what the gcd is, but not how to find it. Factoring $f$ and $g$ is usually hard. Division is easy, and one observation turns division into an algorithm: dividing does not change the ideal.

Lemma 6.2.5 (Dividing Does Not Change the Ideal)

Let $F$ be a field and $f, g, q, r \in F[x]$ with $f = qg + r$ . Then $\langle f, g \rangle = \langle g, r \rangle$ . Consequently $\gcd(f, g) = \gcd(g, r)$ .

Proof. $(\supseteq)$ The ideal $\langle f, g \rangle$ contains $g$ , and $r = f + (-q)g$ by (I2) and (I3). By Proposition 6.2.1, $\langle g, r \rangle \subseteq \langle f, g \rangle$ .

$(\subseteq)$ The ideal $\langle g, r \rangle$ contains $g$ and $f = qg + r$ . By Proposition 6.2.1, $\langle f, g \rangle \subseteq \langle g, r \rangle$ .

Hence the two ideals are equal. The gcd is the canonical generator of the ideal (Definition 6.2.2), and $f, g$ are both zero exactly when $g, r$ are, so $\gcd(f, g) = \gcd(g, r)$ .

Now divide repeatedly. Each division replaces the pair $(f, g)$ by $(g, r)$ , a pair with the same gcd and a smaller second entry.

Theorem 6.2.6 (Euclidean Algorithm)

Let $F$ be a field and $f, g \in F[x]$ with $g \neq 0$ . Put $r_{-1} = f$ and $r_0 = g$ . As long as $r_k \neq 0$ , divide $r_{k-1}$ by $r_k$ (Theorem 6.1.1): $r_{k-1} = q_{k+1} r_k + r_{k+1}, \qquad \deg r_{k+1} < \deg r_k .$ Then:

(a) the process stops: there is an index $n$ with $0 \le n \le \deg g$ such that $r_n \neq 0$ and $r_{n+1} = 0$ ;
(b) if $c$ is the leading coefficient of this last non-zero remainder $r_n$ , then $\gcd(f, g) = c^{-1} r_n$ .

Idea. Two things to see. The degrees $\deg r_0 > \deg r_1 > \deg r_2 > \cdots$ strictly decrease, and natural numbers cannot decrease forever, so some remainder is $0$ . By Lemma 6.2.5, the ideal $\langle r_{k-1}, r_k \rangle$ never changes along the way; at the end it is $\langle r_n, 0 \rangle = \langle r_n \rangle$ , and making $r_n$ monic gives the gcd.

Proof.

(a) As long as $r_1, \dots, r_j$ are all non-zero, their degrees are natural numbers with $\deg g = \deg r_0 > \deg r_1 > \dots > \deg r_j \ge 0$ . So $r_1, \dots, r_j$ are $j$ distinct values in $\{0, 1, \dots, \deg g - 1\}$ , and $j \le \deg g$ . Hence the remainders cannot all be non-zero for $j = \deg g + 1$ : there is a first index $n + 1$ with $r_{n+1} = 0$ , and $n \le \deg g$ . Also $n \ge 0$ since $r_0 = g \neq 0$ .
(b) We show by induction on $k$ that $\langle r_{k-1}, r_k \rangle = \langle f, g \rangle$ for $k = 0, 1, \dots, n + 1$ . For $k = 0$ this is the definition of $r_{-1}, r_0$ . If it holds for some $k \le n$ , then $r_{k-1} = q_{k+1} r_k + r_{k+1}$ , and Lemma 6.2.5 gives $\langle r_k, r_{k+1} \rangle = \langle r_{k-1}, r_k \rangle = \langle f, g \rangle$ .

For $k = n + 1$ this reads $\langle f, g \rangle = \langle r_n, 0 \rangle = \langle r_n \rangle$ . Since $c \neq 0$ , $\langle r_n \rangle = \langle c^{-1} r_n \rangle$ , and $c^{-1} r_n$ is monic. Because $g \neq 0$ , Definition 6.2.2 gives $\gcd(f, g) = c^{-1} r_n$ . This proves the theorem.

If $g = 0$ , no division is needed: $\gcd(f, 0)$ is the monic associate of $f$ (or $0$ ), as in Example (First Greatest Common Divisors) (a).

The algorithm also produces Bézout coefficients. Each remainder is a combination of the previous two, $r_{k+1} = r_{k-1} - q_{k+1} r_k$ , so by induction each remainder is a combination of $f$ and $g$ . Keeping track of the coefficients gives the following procedure.

Algorithm. Extended Euclidean algorithm. Input: $f, g \in F[x]$ with $g \neq 0$ .

Set $(r_{-1}, a_{-1}, b_{-1}) = (f, 1, 0)$ and $(r_0, a_0, b_0) = (g, 0, 1)$ .
For $k = 0, 1, 2, \dots$ , as long as $r_k \neq 0$ : divide $r_{k-1} = q_{k+1} r_k + r_{k+1}$ , and set $a_{k+1} = a_{k-1} - q_{k+1} a_k, \qquad b_{k+1} = b_{k-1} - q_{k+1} b_k .$
When $r_{n+1} = 0$ , let $c$ be the leading coefficient of $r_n$ . Output $\gcd(f, g) = c^{-1} r_n$ and the coefficients $a = c^{-1} a_n$ , $b = c^{-1} b_n$ .

The invariant $r_k = a_k f + b_k g$ holds for $k = -1, 0$ by the choice in step 1. If it holds for $k - 1$ and $k$ , then $r_{k+1} = r_{k-1} - q_{k+1} r_k = (a_{k-1} - q_{k+1} a_k) f + (b_{k-1} - q_{k+1} b_k) g = a_{k+1} f + b_{k+1} g .$ So at the end $\gcd(f, g) = c^{-1} r_n = af + bg$ . By hand, it is often quicker to write each division as “remainder $= \dots$ ” and substitute backwards, which is the same computation.

Example (The Euclidean Algorithm with Back-Substitution)

In $\mathbb{Q}[x]$ , let $f = x^4 - x^3 - 3x^2 + x + 2$ and $g = x^3 - 2x - 1$ . Find $\gcd(f, g)$ and polynomials $a, b$ with $\gcd(f, g) = af + bg$ .

Solution. Divisions. First divide $f$ by $g$ . The leading terms give $x$ , and $f - xg = -x^3 - x^2 + 2x + 2$ ; then $-1$ , and adding $g$ leaves $-x^2 + 1$ . So $f = (x - 1)\,g + r_1, \qquad r_1 = 1 - x^2 .$ Next divide $g$ by $r_1$ . The leading terms give $x^3 / (-x^2) = -x$ , and $g - (-x) r_1 = x^3 - 2x - 1 + x - x^3 = -x - 1$ . So $g = (-x)\, r_1 + r_2, \qquad r_2 = -x - 1 .$ Next divide $r_1$ by $r_2$ . Since $(x - 1)(-x - 1) = -x^2 + 1$ , $r_1 = (x - 1)\, r_2 + 0 .$ The last non-zero remainder is $r_2 = -x - 1$ , with leading coefficient $-1$ . By Theorem 6.2.6, $\gcd(f, g) = x + 1$ .

Back-substitution. From the first two divisions, $r_1 = f - (x - 1) g, \qquad r_2 = g + x\, r_1 .$ Substituting the first into the second, $r_2 = g + x\bigl( f - (x - 1) g \bigr) = x f + (1 + x - x^2)\, g .$ Multiplying by $c^{-1} = -1$ , $x + 1 = (-x)\, f + (x^2 - x - 1)\, g .$ In the notation of the algorithm, $(a_1, b_1) = (1, 1 - x)$ and $(a_2, b_2) = (x, 1 + x - x^2)$ .

Checks. Expanding, $-x(x^4 - x^3 - 3x^2 + x + 2) = -x^5 + x^4 + 3x^3 - x^2 - 2x$ and $(x^2 - x - 1)(x^3 - 2x - 1) = x^5 - x^4 - 3x^3 + x^2 + 3x + 1$ , which sum to $x + 1$ . As an independent check that $x + 1$ divides both, $f(-1) = 1 + 1 - 3 - 1 + 2 = 0$ and $g(-1) = -1 + 2 - 1 = 0$ , so Theorem 6.1.3 applies.

6.2.6. Coprime polynomials

The most important value a gcd can take is $1$ . Then $f$ and $g$ share no non-constant factor, and Bézout’s identity writes $1$ itself as a combination.

Definition 6.2.3 (Coprime Polynomials)

Let $F$ be a field. Polynomials $f, g \in F[x]$ are coprime (or relatively prime) over $F$ if $\gcd(f, g) = 1$ .

Proposition 6.2.7 (Coprime Means 1 Is a Combination)

Let $F$ be a field and $f, g \in F[x]$ . Then $f$ and $g$ are coprime if and only if there exist $a, b \in F[x]$ with $af + bg = 1$ .

Proof. $(\Rightarrow)$ This is Corollary 6.2.4 with $\gcd(f, g) = 1$ .

$(\Leftarrow)$ If $af + bg = 1$ , then $1 \in \langle f, g \rangle$ , so $\langle f, g \rangle = F[x] = \langle 1 \rangle$ by Example (First Ideals) (a). In particular $f, g$ are not both zero, and the monic generator is $1$ . Hence $\gcd(f, g) = 1$ .

Examples: for distinct $c, c' \in F$ , the polynomials $x - c$ and $x - c'$ are coprime, since $(c' - c)^{-1}(x - c) - (c' - c)^{-1}(x - c') = (c' - c)^{-1}(c' - c) = 1 .$ A non-zero constant is coprime to every polynomial (Example (First Greatest Common Divisors) (a)). The polynomial $0$ is coprime only to the non-zero constants. Non-example: $x^2 - 1$ and $x + 1$ are not coprime, since $x + 1$ divides both, so $x + 1 \mid \gcd$ by Theorem 6.2.3 (b), and the gcd has degree at least $1$ .

Coprimality is what lets a divisor pass through a product.

Theorem 6.2.8 (A Coprime Factor Can Be Canceled)

Let $F$ be a field and $p, q, r \in F[x]$ . If $p \mid qr$ and $\gcd(p, q) = 1$ , then $p \mid r$ .

Proof. By Proposition 6.2.7, there are $a, b \in F[x]$ with $ap + bq = 1$ . Multiplying by $r$ , $r = (ar)p + b(qr)$ . Here $p \mid p$ and $p \mid qr$ by hypothesis, so $p \mid r$ by Proposition 6.1.2 (b). This proves the theorem.

Warning. The coprimality hypothesis cannot be dropped. Take $p = x^2$ and $q = r = x$ . Then $p \mid qr = x^2$ , but $p \nmid r$ , since $\deg x^2 > \deg x$ (Proposition 6.1.2 (c)). Here $\gcd(p, q) = x \neq 1$ : part of $p$ is absorbed by $q$ and part by $r$ .

In the next section, Theorem 6.2.8 becomes Euclid’s lemma for irreducible polynomials, which is the heart of unique factorization.

Least common multiples, briefly. For $f, g \in F[x]$ , the intersection $\langle f \rangle \cap \langle g \rangle$ is again an ideal: it contains $0$ , so (I1) holds, and (I2) and (I3) hold in each of $\langle f \rangle$ and $\langle g \rangle$ , hence in the intersection. Its members are the common multiples of $f$ and $g$ .

Definition 6.2.4 (Least Common Multiple)

Let $F$ be a field and $f, g \in F[x]$ . The least common multiple $\operatorname{lcm}(f, g)$ is the monic generator of the ideal $\langle f \rangle \cap \langle g \rangle$ if this ideal is non-zero, and $0$ otherwise.

Exactly as for the gcd, $\operatorname{lcm}(f, g)$ is a common multiple of $f$ and $g$ that divides every common multiple, by Theorem 6.2.2. If $f = 0$ or $g = 0$ , the only common multiple is $0$ ; otherwise $fg$ is a non-zero common multiple. For monic $f$ and $g$ , $\gcd(f, g) \cdot \operatorname{lcm}(f, g) = fg$ ; this is proved in Exercise C3. For example, in $\mathbb{Q}[x]$ , $\gcd(x^2 - 1, x^2 + x - 2) = x - 1$ , so $\operatorname{lcm}(x^2 - 1, x^2 + x - 2) = (x - 1)(x + 1)(x + 2)$ .

6.2.7. The gcd does not depend on the field

A polynomial with rational coefficients is also a polynomial with real and with complex coefficients. Its gcd with another rational polynomial can be computed in $\mathbb{Q}[x]$ , $\mathbb{R}[x]$ or $\mathbb{C}[x]$ , and the definition does not obviously give the same answer, because the coefficients $a, b$ in $\langle f, g \rangle$ range over a larger set. The Euclidean algorithm shows the answers agree. Recall that a subfield $K$ of a field $L$ is a subset closed under the field operations (Definition 1.9.1); then $K[x] \subseteq L[x]$ , with the same addition and multiplication.

Proposition 6.2.9 (The gcd Is the Same Over a Larger Field)

Let $K$ be a subfield of a field $L$ , and let $f, g \in K[x]$ . Then the greatest common divisor of $f$ and $g$ computed in $K[x]$ equals the one computed in $L[x]$ . In particular, $f$ and $g$ are coprime over $K$ if and only if they are coprime over $L$ .

Proof. If $g = 0$ , both gcds are the monic associate of $f$ (or $0$ ), by Example (First Greatest Common Divisors) (a), and this does not depend on the field. Let $g \neq 0$ , and run the Euclidean algorithm in $K[x]$ : $r_{k-1} = q_{k+1} r_k + r_{k+1}$ with $\deg r_{k+1} < \deg r_k$ , all in $K[x]$ . Each of these equations also holds in $L[x]$ , with the same degree condition. By the uniqueness in Theorem 6.1.1 over $L$ , they are exactly the divisions that the algorithm performs in $L[x]$ . So both runs produce the same last non-zero remainder $r_n$ , and Theorem 6.2.6 gives the same gcd $c^{-1} r_n$ in both. This proves the proposition.

Warning. The gcd does not see the field, but factorization does. Over $\mathbb{Q}$ , the polynomial $x^2 - 2$ has no root, by Theorem 0.2.3, so it has no factor $x - c$ with $c \in \mathbb{Q}$ (Theorem 6.1.3). Over $\mathbb{R}$ it factors as $(x - \sqrt2)(x + \sqrt2)$ . Yet $\gcd(x^2 - 2, x^2 - 2x)$ , say, is the same over $\mathbb{Q}$ and over $\mathbb{R}$ . So “coprime” is a robust notion, while “cannot be factored” depends on the field; the next section makes the second notion precise.

A useful consequence: if $f, g \in \mathbb{Q}[x]$ are coprime over $\mathbb{Q}$ , then they have no common root in $\mathbb{C}$ . Indeed, $af + bg = 1$ with $a, b \in \mathbb{Q}[x] \subseteq \mathbb{C}[x]$ , and evaluating at a common root $z$ would give $0 = 1$ by Theorem 0.8.5. So common complex roots can be detected by a computation that never leaves $\mathbb{Q}$ .

6.2.8. Exercises

A. Check your understanding

Exercise (A1)

(a) Define an ideal of $F[x]$ .
(b) State the theorem describing all ideals of $F[x]$ .
(c) Determine whether the following statement is true: “for all $f, g \in F[x]$ , $\operatorname{span}(f, g) = \langle f, g \rangle$ .” Justify your answer.
(d) Is $\gcd(2x - 2, 4x^2 - 4) = 2x - 2$ in $\mathbb{Q}[x]$ ? Justify your answer.
(e) Determine whether the following statement is true: “if $af + bg = x - 1$ for some $a, b \in \mathbb{Q}[x]$ , then $\gcd(f, g) = x - 1$ .” Justify your answer.
(f) Name an algorithm that computes $\gcd(f, g)$ using only division with remainder (Theorem 6.1.1).

Solution.

(a) A subset $I \subseteq F[x]$ is an ideal if it is non-empty, $f + g \in I$ for all $f, g \in I$ , and $hf \in I$ for all $f \in I$ and every $h \in F[x]$ (Definition 6.2.1).
(b) If $I \neq \{0\}$ is an ideal of $F[x]$ , there is exactly one monic $d$ with $I = \langle d \rangle$ , namely the monic polynomial of least degree in $I$ (Theorem 6.2.2).
(c) False. Take $f = g = x$ . Then $\operatorname{span}(x, x) = \{ cx : c \in F \}$ does not contain $x^2$ , while $x^2 = x \cdot x \in \langle x, x \rangle$ . The span allows only scalar coefficients.
(d) No. The gcd is monic by definition. Since $4x^2 - 4 = (2x - 2)(2x + 2)$ , we have $\langle 2x - 2, 4x^2 - 4 \rangle = \langle 2x - 2 \rangle = \langle x - 1 \rangle$ , so the gcd is $x - 1$ .
(e) False. Take $f = x$ and $g = x - 1$ , with $a = 0$ , $b = 1$ . Then $af + bg = x - 1$ , but $\gcd(x, x - 1) = 1$ , because $x - (x - 1) = 1$ (Proposition 6.2.7). What is true is that $\gcd(f, g)$ divides every combination $af + bg$ , by Theorem 6.2.3 (a) and Proposition 6.1.2 (b).
(f) The Euclidean algorithm (Theorem 6.2.6).

B. Practice

Exercise (B1: gcd and Bézout Coefficients of Two Cubics)

In $\mathbb{Q}[x]$ , let $f = x^3 + x^2 + x + 1$ and $g = x^3 + x + 2$ . Use the Euclidean algorithm to find $d = \gcd(f, g)$ and polynomials $a, b \in \mathbb{Q}[x]$ with $d = af + bg$ . Hence find all complex numbers that are roots of both $f$ and $g$ .

Solution. Divide $f$ by $g$ : $f = 1 \cdot g + r_1$ with $r_1 = f - g = x^2 - 1$ . Divide $g$ by $r_1$ : $x \cdot r_1 = x^3 - x$ , and $g - x r_1 = 2x + 2$ , so $g = x\, r_1 + r_2$ with $r_2 = 2x + 2$ . Divide $r_1$ by $r_2$ : $x^2 - 1 = \tfrac12 (x - 1)(2x + 2) + 0$ . The last non-zero remainder is $r_2 = 2x + 2$ , with leading coefficient $2$ , so $d = x + 1$ by Theorem 6.2.6.

Back-substituting, $r_2 = g - x r_1 = g - x(f - g) = -x f + (1 + x) g$ . Dividing by $2$ , $x + 1 = \Bigl( -\frac{x}{2} \Bigr) f + \frac{x + 1}{2}\, g .$ Check: $-\tfrac{x}{2}(x^3 + x^2 + x + 1) + \tfrac{x+1}{2}(x^3 + x + 2)$ equals $\tfrac12\bigl( -x^4 - x^3 - x^2 - x + x^4 + x^3 + x^2 + 3x + 2 \bigr) = x + 1 .$

Hence: let $z \in \mathbb{C}$ . If $f(z) = g(z) = 0$ , then evaluating the identity above in $\mathbb{C}$ (Theorem 0.8.5) gives $z + 1 = 0$ . Conversely, $x + 1$ divides $f$ and $g$ (Theorem 6.2.3 (a)), so $-1$ is a root of both. Therefore $-1$ is the only common complex root.

Exercise (B2: Ideal or Not?)

Determine which of the following subsets of $\mathbb{R}[x]$ are ideals. For each ideal, find its monic generator. Justify your answers.

(a) $S_1 = \{ f \in \mathbb{R}[x] : f(1) = f(-1) \}$ .
(b) $S_2 = \{ f \in \mathbb{R}[x] : f(0) = 0 \text{ and } f(1) = 0 \}$ .
(c) $S_3 = \{ f \in \mathbb{R}[x] : \deg f \ge 3 \} \cup \{0\}$ .
(d) $S_4 = \{ f \in \mathbb{R}[x] : f(i) = 0 \}$ , where $f(i)$ means the value at $i \in \mathbb{C}$ of $f$ regarded as a complex polynomial.

Solution.

(a) Not an ideal. $S_1$ is a subspace, and $1 \in S_1$ . But $x \cdot 1 = x$ has $x(1) = 1 \neq -1 = x(-1)$ , so $x \notin S_1$ , and (I3) fails.
(b) An ideal. The argument of Example (First Ideals) (b), applied at both points, gives (I1)–(I3). If $f \in S_2$ , then $0$ and $1$ are distinct roots of $f$ , so $x(x - 1) \mid f$ by Corollary 6.1.4. Conversely every multiple of $x^2 - x$ vanishes at $0$ and $1$ . Hence $S_2 = \langle x^2 - x \rangle$ , with monic generator $x^2 - x$ .
(c) Not an ideal. $x^3 \in S_3$ and $-x^3 + x \in S_3$ , but their sum $x$ has degree $1$ and is non-zero, so (I2) fails.
(d) An ideal: evaluation at $i$ respects sums and products (Theorem 0.8.5 over $\mathbb{C}$ ), so the argument of Example (First Ideals) (b) applies. It contains $x^2 + 1$ . A non-zero element of degree at most $1$ would be $a + bx$ with $a, b \in \mathbb{R}$ not both zero and $a + bi = 0$ , which is impossible since the real and imaginary parts give $a = b = 0$ . So the least degree of a non-zero element is $2$ . If $d$ is the monic generator (Theorem 6.2.2), then $\deg d = 2$ and $d \mid x^2 + 1$ , so $x^2 + 1 = ud$ with $u$ constant, and comparing leading coefficients gives $u = 1$ . Hence $S_4 = \langle x^2 + 1 \rangle$ .

Exercise (B3: The gcd of

x^m - 1

and

x^n - 1

)

Let $F$ be a field. For integers $m, n \ge 0$ , not both zero, let $\gcd(m, n)$ denote the largest positive integer dividing both.

(a) For $m \ge n \ge 1$ , verify that $x^m - 1 = x^{m-n}(x^n - 1) + (x^{m-n} - 1)$ .
(b) Prove that $\gcd(x^m - 1, x^n - 1) = x^{\gcd(m, n)} - 1$ in $F[x]$ for all $m, n \ge 0$ not both zero, where $x^0 - 1 = 0$ .
(c) Hence compute $\gcd(x^{12} - 1, x^{18} - 1)$ .

Hint for (b): Theorem 6.2.6, run on the exponents.

Solution.

(a) Expanding, $x^{m-n}(x^n - 1) + x^{m-n} - 1 = x^m - x^{m-n} + x^{m-n} - 1 = x^m - 1$ .
(b) We use strong induction on $s = m + n \ge 1$ (Theorem 0.2.10). If $n = 0$ , then $m \ge 1$ , $\gcd(m, 0) = m$ , and $\gcd(x^m - 1, 0)$ is the monic associate of $x^m - 1$ , which is $x^m - 1$ itself (Example (First Greatest Common Divisors) (a)). The case $m = 0$ is the same, since both gcds are symmetric. Now let $m, n \ge 1$ ; by symmetry we may assume $m \ge n$ . By (a) and Lemma 6.2.5, $\gcd(x^m - 1, x^n - 1) = \gcd(x^n - 1, x^{m-n} - 1) .$ The pair $(n, m - n)$ is not both zero and has sum $m < m + n$ , so by the induction hypothesis the right side is $x^{\gcd(n, m - n)} - 1$ . Finally, $\gcd(n, m - n) = \gcd(m, n)$ : if $k \mid m$ and $k \mid n$ , then $k \mid m - n$ ; and if $k \mid n$ and $k \mid m - n$ , then $k \mid (m - n) + n = m$ . So the two pairs have the same positive common divisors, and the same largest one. This completes the induction.
(c) By (b), $\gcd(x^{12} - 1, x^{18} - 1) = x^{\gcd(12, 18)} - 1 = x^6 - 1$ .

C. Going deeper

Exercise (C1: Polynomials Vanishing on a Set)

Let $F$ be a field and $S \subseteq F$ non-empty. Put $I(S) = \{ f \in F[x] : f(s) = 0 \text{ for all } s \in S \}$ .

(a) Prove that $I(S)$ is an ideal of $F[x]$ .
(b) Suppose $S = \{ s_1, \dots, s_k \}$ is finite, with the $s_i$ distinct. Prove that $I(S) = \langle (x - s_1) \cdots (x - s_k) \rangle$ .
(c) Suppose $S$ is infinite. Prove that $I(S) = \{0\}$ .
(d) Deduce from (b) and Exercise (C3: Equal Functions Over $\mathbb{F}_p$ ) that $I(\mathbb{F}_p) = \langle x^p - x \rangle$ for every prime $p$ .

Solution.

(a) The zero polynomial vanishes everywhere, so $I(S) \neq \varnothing$ . If $f, g \in I(S)$ and $h \in F[x]$ , then for every $s \in S$ , Theorem 0.8.5 gives $(f + g)(s) = 0 + 0 = 0$ and $(hf)(s) = h(s) \cdot 0 = 0$ . So (I2) and (I3) hold.
(b) Let $P = (x - s_1) \cdots (x - s_k)$ . Every multiple $hP$ vanishes at each $s_i$ , since $P(s_i) = 0$ ; so $\langle P \rangle \subseteq I(S)$ . Conversely, if $f \in I(S)$ , then $s_1, \dots, s_k$ are distinct roots of $f$ , and Corollary 6.1.4 gives $P \mid f$ . Hence $I(S) = \langle P \rangle$ , and since $P$ is monic, it is the monic generator.
(c) Let $f \in I(S)$ , and suppose $f \neq 0$ . Since $S$ is infinite, it contains $\deg f + 1$ distinct elements, all roots of $f$ . This contradicts Corollary 6.1.4. Hence $f = 0$ .
(d) By (b), $I(\mathbb{F}_p) = \langle P \rangle$ with $P = \prod_{c \in \mathbb{F}_p} (x - c)$ . The solution of Exercise (C3: Equal Functions Over $\mathbb{F}_p$ ) (a) showed $P = x^p - x$ . Hence $I(\mathbb{F}_p) = \langle x^p - x \rangle$ .

Exercise (C2: A Non-Principal Ideal in Two Variables)

A polynomial in two variables over $F$ is a finite sum $P = \sum_{i, j} a_{ij} x^i y^j$ with $a_{ij} \in F$ , only finitely many non-zero; two are equal when all coefficients agree. They are added coefficient by coefficient and multiplied by expanding and collecting, and the set $F[x, y]$ of all of them satisfies the laws of Theorem 0.8.1, which you may use. Ideals of $F[x, y]$ and $\langle P_1, \dots, P_k \rangle$ are defined exactly as in Definition 6.2.1, and Proposition 6.2.1 holds with the same proof. For $P \neq 0$ , let $\deg_y P$ be the largest $j$ with $a_{ij} \neq 0$ for some $i$ , and define $\deg_x P$ similarly.

(a) Prove that $\deg_y(PQ) = \deg_y P + \deg_y Q$ for non-zero $P, Q \in F[x, y]$ . By symmetry the same holds for $\deg_x$ .
(b) Show that $\langle x, y \rangle$ consists of the polynomials whose constant coefficient $a_{00}$ is $0$ .
(c) Prove that $\langle x, y \rangle \neq \langle D \rangle$ for every $D \in F[x, y]$ .
(d) Explain precisely which step of the proof of Theorem 6.2.2 has no analogue in $F[x, y]$ .

Hint for (a): write $P = \sum_{j} p_j(x) y^j$ with $p_j \in F[x]$ , and use Corollary 0.8.4.

Solution.

(a) Group terms by the power of $y$ : $P = \sum_{j=0}^{s} p_j y^j$ and $Q = \sum_{j=0}^{t} q_j y^j$ with $p_j, q_j \in F[x]$ , $s = \deg_y P$ , $t = \deg_y Q$ , so $p_s \neq 0$ and $q_t \neq 0$ . Expanding, the terms of $PQ$ with $y$ -power greater than $s + t$ are all zero, and the terms with $y^{s+t}$ come only from $p_s y^s \cdot q_t y^t$ , giving $(p_s q_t) y^{s+t}$ . By Corollary 0.8.4, $p_s q_t \neq 0$ in $F[x]$ , so some coefficient of $x^i y^{s+t}$ in $PQ$ is non-zero. Hence $\deg_y(PQ) = s + t$ .
(b) Every $Ax + By$ has constant coefficient $0$ , since each term of $Ax$ and $By$ involves $x$ or $y$ to a positive power. Conversely, if $a_{00} = 0$ , then every term $a_{ij}x^iy^j$ with $i \ge 1$ is a multiple of $x$ , and every term with $i = 0$ , $j \ge 1$ is a multiple of $y$ . Grouping them, $P = Ax + By$ for some $A, B \in F[x, y]$ .
(c) Suppose $\langle x, y \rangle = \langle D \rangle$ . Since $x \in \langle D \rangle$ , $x = HD$ for some $H$ , so $D \neq 0$ and $H \neq 0$ . By (a), $0 = \deg_y x = \deg_y H + \deg_y D$ , so $\deg_y D = 0$ : $D$ involves no $y$ . Similarly $y = KD$ gives $\deg_x D = 0$ . So $D$ is a non-zero constant. But $D \in \langle x, y \rangle$ , so its constant coefficient is $0$ by (b), that is, $D = 0$ . This contradiction shows that $\langle x, y \rangle$ is not principal.
(d) The proof of Theorem 6.2.2 picks a non-zero $d \in I$ of least degree, writes each $f \in I$ as $f = qd + r$ with $r$ smaller than $d$ by Theorem 6.1.1, notes $r = f - qd \in I$ , and concludes $r = 0$ from minimality. Measure size in $F[x, y]$ by the total degree, the largest $i + j$ with $a_{ij} \neq 0$ . Choosing $d$ still works: by (b), every non-zero element of $\langle x, y \rangle$ has total degree at least $1$ , and those of total degree $1$ are the $ax + by$ with $(a, b) \neq (0, 0)$ . Let $d$ be any of them. Then $\langle d \rangle \subseteq \langle x, y \rangle$ by (I3), and the inclusion is strict by (c), so some $f \in \langle x, y \rangle$ is not a multiple of $d$ . For this $f$ and every $Q \in F[x, y]$ , the element $R = f - Qd$ lies in $\langle x, y \rangle$ and is non-zero, so its total degree is at least $1$ , the total degree of $d$ . So no remainder smaller than $d$ exists: the step with no analogue is division with remainder, the appeal to Theorem 6.1.1. Concretely, for $d = x$ and $f = y$ , every term of $Qx$ contains $x$ , so the term $y$ survives in $y - Qx$ . The underlying reason is that, viewed as a polynomial in $y$ with coefficients in $F[x]$ , the leading coefficient $x$ of $d$ is not invertible in $F[x]$ , which is exactly the obstacle of the warning after Theorem 6.1.1.

Exercise (C3: gcd Times lcm)

Let $F$ be a field and $f, g \in F[x]$ monic. Put $d = \gcd(f, g)$ and write $f = d f_1$ , $g = d g_1$ with $f_1, g_1 \in F[x]$ .

(a) Prove that $\gcd(f_1, g_1) = 1$ .
(b) Prove that $m = d f_1 g_1$ is a monic common multiple of $f$ and $g$ that divides every common multiple of $f$ and $g$ .
(c) Deduce that $\operatorname{lcm}(f, g) = d f_1 g_1$ , and hence $\gcd(f, g) \cdot \operatorname{lcm}(f, g) = fg$ .
(d) Show by an example in $\mathbb{Q}[x]$ that the formula in (c) fails if $f$ and $g$ are not monic.

Hint for (b): use Theorem 6.2.8.

Solution.

(a) The quotients exist by Theorem 6.2.3 (a), and $d \neq 0$ since $f \neq 0$ . By Corollary 6.2.4, $d = af + bg = d(af_1 + bg_1)$ . Canceling $d \neq 0$ (Corollary 0.8.4 (2)) gives $af_1 + bg_1 = 1$ , so $\gcd(f_1, g_1) = 1$ by Proposition 6.2.7.
(b) Comparing leading coefficients in $f = d f_1$ with $f, d$ monic shows $f_1$ is monic; likewise $g_1$ . So $m$ is monic, and $m = f g_1 = g f_1$ is a common multiple. Let $M$ be any common multiple, say $M = fu$ . Since $g \mid M$ , write $M = gv$ . Then $d f_1 u = d g_1 v$ , and canceling $d$ gives $f_1 u = g_1 v$ , so $g_1 \mid f_1 u$ . By (a) and Theorem 6.2.8, $g_1 \mid u$ , say $u = g_1 w$ . Hence $M = f g_1 w = m w$ , and $m \mid M$ .
(c) By (b), $m \in \langle f \rangle \cap \langle g \rangle$ , and every element of this ideal is a multiple of $m$ . So $\langle f \rangle \cap \langle g \rangle = \langle m \rangle$ , and $m$ is monic, hence $\operatorname{lcm}(f, g) = m$ by Definition 6.2.4 and Theorem 6.2.2. Then $\gcd(f, g) \cdot \operatorname{lcm}(f, g) = d \cdot d f_1 g_1 = (d f_1)(d g_1) = fg$ .
(d) Take $f = g = 2x$ . Then $\gcd(f, g) = x$ and $\operatorname{lcm}(f, g) = x$ , both monic, so their product is $x^2$ , while $fg = 4x^2$ . In general the two sides differ by the product of the leading coefficients.