Section 1: Rings and Fields



Section 5: Divisibility in F[x], greatest common divisor, and the Euclidean Algorithm

HW p. 14 # 1-6 at the end of the notes

In this section, we examine the divisibility of polynomials more closely and examine what is meant by the greatest common divisor of two polynomials.

Divisibility of Two Polynomials Over a Field

Recall the division algorithm for the polynomial ring[pic], where F is a field, says that for [pic], with [pic], that there exists unique polynomials [pic] where [pic] where either [pic] or [pic]. We want to examine more closely the case where the remainder [pic].

Definition 5.1: Let F be a field and[pic], with [pic]. We say that [pic]

divides [pic](or [pic] is a factor) of [pic]) and write [pic], if [pic] for some [pic].

For example, since [pic] in [pic]since [pic] Also, every constant multiple of [pic] divides [pic]. For example, [pic] divides [pic] since [pic].

Facts

1. If [pic], the [pic] for every non-zero [pic].

Proof:

2. Every divisor of a polynomial [pic] has degree less than or equal to [pic].

Recall that the [pic] of two positive integers a and b is the largest positive integer that divides a and b evenly. To find the [pic] for two polynomials[pic], we look for the polynomial that divides both [pic]

and [pic] of highest degree. However, since, as we saw from Fact 1 above that if [pic], the [pic] for every non-zero [pic], we require the greatest common divisor to be monic, that is, we require its leading coefficient to be 1. This assures that the greatest common divisor of two polynomials is unique. This is summarized in the following definition.

Definition 5.2: Let F be a field and [pic], where [pic] or [pic]. The greatest common divisor of [pic] and [pic], denoted by [pic], is the monic polynomial [pic]of highest degree that both divides both [pic] and [pic]. In mathematical notation, we say that [pic] if [pic] is monic and

(i) [pic] and [pic].

(ii) If [pic] and [pic], then [pic].

One method for finding the greatest divisor of two polynomials is to multiply the irreducible factors they have in common. We demonstrate with the following example.

Example 1: Find the greatest common divisor of the two polynomials [pic] and [pic] in [pic]

Solution: It can be verified that these polynomials have the following factorizations:

[pic]

[pic].

The common factors of both polynomials are

[pic]

Note that the [pic] is factored to satisfy the requirement that the greatest common divisor is require to be monic. Hence,

[pic][pic].

█

The Euclidean Algorithm for Polynomials in F[x]

To more efficiently find the greatest common of two polynomials, we can use the Euclidean Algorithm. The algorithm works similarly to how it works over the integers. Note that the last non-zero remainder may not be monic. However, by the greatest common divisor can be found simplify by factoring the constant from the leading coefficient of the last non-zero remainder. We state the algorithm as follows:

The Euclidean Algorithm

The Euclidean Algorithm makes repeated use of the division algorithm to find the greatest common divisor of two polynomials. If we are given two polynomials in [pic] where [pic], then if [pic], then [pic], where [pic] is the monic polynomial obtained by factoring the leading coefficient of[pic]. If [pic], then we compute

[pic]

The[pic], where [pic] is the monic polynomial obtained by factoring the leading coefficient of the last non-zero remainder [pic].

Example 2: Use the Euclidean Algorithm to find the greatest common divisor of the two polynomials [pic] and [pic] in [pic].

Solution:

█

Example 3: Use the Euclidean Algorithm to find the greatest common divisor of the two polynomials [pic] and [pic] in [pic].

Solution:

█

Theorem 5.3: For a field F, for any two polynomials [pic], there are polynomials [pic] and [pic]where

[pic]

Fact: When executing the Euclidean algorithm equations,

[pic]

We can create a table to determine the [pic], [pic], and [pic] as follows:

[pic][pic]

Notes

1. The quotients under Q and remainders under R are computed using the basic Euclidean

algorithm process. The table is complete when [pic]. The last non-zero remainder [pic] is used to find the greatest common divisor of [pic] and [pic] by converting [pic], to a monic polynomial by factoring its leading coefficient. This monic polynomial [pic]is the greatest common divisor, that is [pic].

2. The [pic] under U and [pic] under V are found using the formulas

[pic].

3. For row i, we have [pic]. The values u and v where [pic] are found in the last row where

[pic].

The polynomials [pic]and [pic] are found by multiplying both sides of this equation by the multiplicative inverse of the leading coefficient of [pic] to obtain a monic polynomial for the greatest common divisor.

Example 4: Use an Euclidean Algorithm table to find polynomials [pic] and [pic] where [pic] for the two polynomials [pic] and [pic] in [pic].

Solution:

█

Example 5: Use an Euclidean Algorithm table to find polynomials [pic] and [pic] where [pic] for the two polynomials [pic] and [pic] in [pic].

Solution: First, we run the Euclidean Algorithm to show that [pic] using the following process: (note that the result is a monic polynomial)

[pic]

Setting [pic] and [pic] and [pic] and using the equations

[pic]

gives the following calculation for each row.

[pic], [pic]

[pic].

[pic], [pic].

[pic]

[pic], [pic].

[pic]

The previous results give the following Euclidean Algorithm Table:

[pic]

continued on next page

From the last row, we see that [pic] and [pic] This answer can be verified by checking

[pic].

█

The following is a corollary resulting from the above results.

Corollary 5.4: Let F be a field and [pic], not both zero. A monic polynomial [pic] is the greatest common divisor of [pic] and [pic] if and only if [pic] satisfies these conditions.:

(i) [pic] and [pic].

(ii) if [pic] and [pic], then [pic].

Proof: [pic] Suppose [pic] is the greatest common divisor of [pic] and [pic]. By definition of the greatest common divisor, [pic] and [pic]. Also, we know there exists [pic] such that

[pic] *

Now, if if [pic] and [pic], then, by definition of divisibility, there exist polynomials [pic] where

[pic][pic] and [pic] **

Substituting the results of ** into * gives

[pic]

or

[pic]

Hence, [pic].

[pic] Suppose [pic] satisfies conditions (i) and (ii). By condition (i), [pic] is a common divisor of both [pic] and [pic]. Condition (ii) says [pic] must be the divisor of highest degree since if [pic], then [pic]. Thus, [pic] is the greatest common divisor of [pic] and [pic].

█

Note: Two polynomials [pic] and [pic] are said to be relatively prime if [pic].

Theorem 5.5: Let F be a field and [pic]. If [pic] and [pic]

and [pic] are relatively prime, then [pic].

Proof:

█

Exercises

1. Use the Euclidean Algorithm to find the greatest common divisor of the given polynomials.

a. [pic] and [pic] in [pic].

b. [pic] and [pic] in [pic].

c. [pic] and [pic] in [pic].

d. [pic] and [pic] in [pic].

e. [pic] and [pic] in [pic].

f. [pic] and [pic] in [pic].

2. For each exercise for Exercise 1, assign a and b and generate an Euclidean algorithm table to find polynomials [pic] and [pic] where [pic].

3. Find [pic] in [pic].

4. For a field F, let [pic] and suppose [pic]. If [pic]

and [pic], prove that [pic].

5. For a field F, let [pic] and suppose [pic]. If [pic], prove that [pic].

6. For a field F, let [pic] and suppose [pic]. Prove that

[pic].

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download