# 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^{3} - 3x^{2} - 6x, b(x) = 2x^{2} - 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.

Prev | Next |