Polynomials

3.3 Unique Factorization of Polynomials

Because the division algorithm does not always work for Z[x], from now on we only consider polynomials
over Q and R.

As we have discussed, a nonzero integer as a unique prime factorization “up to factors of ±1.” Similarly,
polynomials in Q [x] and R[x] can be uniquely factorized into irreducible polynomials “up to factors of
units”:

Theorem 2. Let D = Q or R.

Let p(x) be a nonconstant polynomial in D[x], and suppose that are irreducible polynomials so that

Then if are also irreducible polynomials so that .

Then l = m, and can be ordered so that

where are units of D[x].

Restricting D to Q or R allows the division of a polynomial by its leading coefficient to be an element of
D[x]. When we divide a polynomial by its leading coefficient, the result is a monic polynomial: one whose
leading coefficient is 1.

Another formulation of Theorem 2 is:

Theorem 3 (Theorem 5.21 in textbook). Every nonconstant polynomial in D[x] can be represented as a product

where a ∈ D, and are monic, irreducible polynomials in D[x]. This factorization is unique.

4 GCFs and the Euclidean Algorithm for Polynomials

As in the previous section , we let D = Q or R so that we can assume the ability to perform the division
algorithm.

4.1 Greatest Common Factors of polynomials

Definition 4. Given a(x), b(x) ∈ D[x] (not both zero), a polynomial d(x) ∈ D[x] is a greatest common factor of
a(x) and b(x) if

• d(x) is a factor of a(x) and b(x)

• any common factor of a(x) and b(x) is a factor of d(x).

We use the notation gcf(a(x), b(x)) to denote the unique monic polynomial that is a greatest common factor of a(x)
and b(x).

Example. Let a(x) = 3x³ - 3x² - 6x, b(x) = 2x² - 2. Then

a(x) = 3x(x + 1)(x - 2) and b(x) = 2(x - 1)(x + 1).

Under the above definition, any polynomial of the form k(x + 1), where k ∈D is a greatest common factor of a(x)
and b(x). However, we set gcf(a(x), b(x)) = x + 1.

4.2 The Euclidean Algorithm for Polynomials

Recall the key observations we needed to show that (1) the Euclidean Algorithm yielded the GCF, and (2)
the algorithm terminated after a finite number of iterations:

(1) If c is a common factor of a and b, then c is a factor of any integer linear combination of a and b .

This observation allowed us to show that when a, b, q, r ∈ Z satisfy a = bq + r, then gcf(a, b) = gcf(b, r).
Hence, the gcf of the dividend and divisor for every step of the Euclidean Algorithm is the same.

(2) The Well-Ordering Principle: Every subset of the natural numbers has a unique smallest element.

The Euclidean Algorithm, performed on a, b ∈ Z (not both zero ), terminates when the remainder at a step
is 0. To show that the remainder eventually reaches 0, we consider the sequence of remainders, which is
strictly decreasing. Since each remainder is a natural number, the sequence of remainders has a unique
smallest element. If a remainder is nonzero, we must continue performing the Euclidean Algorithm. However,
the sequence cannot continue forever without reaching 0, by the Well-Ordering Principle. Hence the
sequence of remainders must reach 0 after a finite number of steps.

The justification for the Euclidean Algorithm for Polynomials is very similar, although there is a little more
bookkeeping involved.

Lemma 1a. If c(x) is a common factor of a(x) and b(x) inD[x], then c is a factor of any polynomial linear combination
of a(x) and b(x), where the coefficients of the linear combination are taken in D[x].

(Recall that a polynomial linear combination of a(x) and b(x) is a sum of the form p(x)a(x) + q(x)b(x);
in the above lemma, we take p(x), q(x)∈ D[x]. The polynomials p(x) and q(x) are the coefficients of the
linear combination of a(x) and b(x). )

Proof of Lemma 4.2. If c(x) is a factor of a(x) and b(x) in D[x], then there exist a'(x) and b'(x) so that a(x) =
c(x)a'(x) and b(x) = c(x)b'(x).

Choose p(x), q(x) ∈ D[x]. Then the c(x) is a factor of p(x)a(x) + q(x)b(x) in D[x], as

p(x)a(x) + q(x)b(x) = p(x)c(x)a'(x) + q(x)c(x)b'(x) = c(x)(p(x)a'(x) + q(x)b'(x)).

The polynomial p(x)a'(x) + q(x)b'(x) is an element of D[x] as each of its constituent terms are elements of
D[x] as well.

Lemma 1b (Corollary of Lemma 1a). If a(x) = b(x)q(x) + r(x), then gcf(a(x), b(x)) = gcf(b(x), r(x)).

The proof of this lemma follows the same lines as the analogous lemma for integers.

Theorem 4 (Theorem 5.20 in text). Given two polynomials a(x), b(x) ∈ D[x] (not both zero), with deg(a(x)) ≥
deg(b(x)), we may find gcf(a, b) using the following algorithm:

Step 1. Let q(x) and r(x) be the unique polynomials in D[x] so that

a(x) = b(x)q(x) + r(x) and deg(r(x)) < deg(b(x)).

Step 2. If r(x) = 0, then STOP; the greatest common factor is b(x), where k is the leading coefficient of b(x).
Otherwise, replace a(x) with b(x), and replace b(x) with r(x), and return to Step 1.

As the proof for the Euclidean Algorithm for Polynomials is close to the proof for the Euclidean Algorithm
for Integers, we don’t include it. However, we observe that the main idea behind showing that the algorithm
terminates after a finite number of iterations is examining the sequence of degrees of the remainder
polynomials appearing in the steps.