Try our Free Online Math Solver!

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 WellOrdering 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 WellOrdering 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 