📚 The CoCalc Library - books, templates and other resources

cocalc-examples / paulsen-abstract-algebra / ring12.ipynb

¹³²⁹²² views
License: OTHER

Kernel: SageMath (stable)

Abstract Algebra: An Interactive Approach, 2e

Chapter 12
Unique Factorization

Initialization: This cell MUST be evaluated first:

In [0]:

%display latex
try:
    load('absalgtext.sage')
except IOError:
    load('/media/sf_sage/absalgtext.sage')

Factorization of Polynomials
Unique Factorization Domains
Principal Ideal Domains
Euclidean Domains
Sage Interactive Problems

Factorization of Polynomials

In the last chapter, we saw how we could create an integral domain from a field F by considering all polynomials using the variable x with coefficients in F. We called this ring F[x]. In this section we want to investigate how such polynomials would factor. Most of the statements in this section are very familiar from the properties of polynomials ℚ[x] studied in a standard algebra course.

We say that f(x) factors if there are two non-constant polynomials g(x) and h(x) such that f(x) = g(x)·h(x). We also say that both g(x) and h(x) divide the polynomial f(x). But g(x) and h(x) may also factor into non-constant polynomials. We want to show that we can factor f(x) into polynomials that cannot be factored further. We also want to lay down the groundwork for showing that the polynomials produced by this factorization are in some sense uniquely determined.

One the the techniques learned in algebra is that we can do "long division" on polynomials. A sample problem would be (x³ − 3 x² + 4 x − 5) divided by (2 x² − 5). Using long division, we have:

						¹⁄₂ x	−	3/2
	___________________________
2 x² − 5	)	x³	−	3 x²	+	4 x	−	5
		x³			−	⁵⁄₂ x

			−	3 x²	+	¹³⁄₂ x	−	5
			−	3 x²			+	¹⁵⁄₂

						¹³⁄₂ x	−	²⁵⁄₂

Thus, x³ − 3 x² + 4 x − 5 divided by 2 x² − 5 yields ¹⁄₂ x − ³⁄₂, with a remainder of ¹³⁄₂ x − ²⁵⁄₂. We can write this as

(x³ − 3 x² + 4 x − 5) = (2 x² − 5)·(¹⁄₂ x − ³⁄₂) + (¹³⁄₂ x − ²⁵⁄₂).

Fortunately, Sage has two commands which performs this tedious long division for you:

In [0]:

var("x")
PolynomialQuotient(x^3 - 3*x^2 + 4*x - 5, 2*x^2 - 5)

In [0]:

PolynomialRemainder(x^3 - 3*x^2 + 4*x - 5, 2*x^2 - 5)

EXPERIMENT:
Try replacing the polynomials in the last two statements with different polynomials in x. What do you observe about the degree of the remainder in comparison to the degree of the divisor?

This "long division" algorithm works for any field, not just the rational numbers ℚ. We can prove this by induction on the degree of the dividend.

THEOREM 12.1:The Division Algorithm Theorem
Let F be a field, and let F[x] be the set of polynomials in x over F. Let f(x) and g(x be two elements of F[x], with g nonzero. Then there exist unique polynomials q(x) and r(x)in F[x] such that

f(x) = g(x)·q(x) + r(x)

and either r(x) = 0 or the degree of r(x) is less than the degree of g(x).

Click here for the proof.

COROLLARY 12.1
Let R be an integral domain, and let f(x) and g(x) be two polynomials in R[x]. If there is a field F containing R such that g(x) divides f(x) as polynomials in F[x], and if the leading coefficient of g(x) is 1, then g(x) divides f(x) in R[x].

Click here for the proof.

We are used to thinking of polynomials as functions, rather than as elements in a domain. If we want to "evaluate" a polynomial f(x) at a particular value y, we run into a technical problem, since f(x) is not a function. The division algorithm comes to our rescue on the occasions when we do need to evaluate polynomials at a particular value.

DEFINITION 12.1
Let K be a field or integral domain, and let K[x] be the set of polynomials in x over K. For a fixed element y in K, define the mapping

ϕ_y : K[x] → K

ϕ_y( f(x) ) = the remainder r(x) when f(x) is divided by (x − y).

Since the polynomial (x − y) is first degree, either r(x) is 0 or is of degree 0, so r(x) is in fact in K.

PROPOSITION 12.1
The mapping ϕ_y : K[x] → K is a homomorphism, called the evaluation homomorphism at y.

Click here for the proof.

We will often denote ϕ_y(f(x)) by the conventional notation, f(y). However, whenever we want to emphasize the homomorphism property, we will use the notation ϕ_y(f(x)) for the evaluation homomorphism. This homomophism can be used in Sage with the command .subs(). To evaluate the polynomial x³ + 5 x² + 4 x − 4 at x = 3, enter

In [0]:

var("x")
(x^3 + 5*x^2 + 4*x - 4).subs(x == 3)

Sage also can use the standard functional notation:

In [0]:

f(x) = x^3 + 5*x^2 + 4*x - 4

In [0]:

f(3)

The difference here is that Sage is actually defining a simple function, and evaluating the function at x = 3.

EXPERIMENT:
Try changing the 3 in the above command with different integers. Can you find an integer for which the polynomial evaluates to 0?

This experiment shows how we can use the evaluation homomorphism to define what it means for a polynomial to have a root.

DEFINITION 12.2
Let f(x) be a polynomial over the field or integral domain F. If r is an element of F such that ϕ_r(f(x)) = 0, then r is called a zero, or a root, of f(x). Of course this is equivalent to saying that (x − r) is a factor of f(x).

EXAMPLE:
Consider the polynomial x² + 1 in Z₅[x]. We can visually evaluate this polynomial at x = 2 to see that

ϕ₂(x² + 1) = 2² + 1 ≡ 0

in the field Z₅. Thus, 2 is a root, or a zero, of x² + 1.

EXPERIMENT:
Since 2 is a root, (x − 2) must be a factor of x² + 1. What is the other factor?

As one can imagine, the factorization of a polynomial over an arbitrary field can be more cumbersome than the customary factorization. For a finite field (such as Z₅), almost the only way to find roots is by trial and error. Fortunately, Sage can do this very quickly. However, the good news is that if we have found enough roots to a polynomial, we already have the factorization.

PROPOSITION 12.2
Let f(x) be a polynomial over the field F that has positive degree n and leading coefficient a_n. If r₁, r₂, r₂, … r_n are n distinct zeros of f(x), then

f(x) = a_n·(x − r₁)·(x − r₂)·(x − r₃)⋯(x − r_n).

Click here for the proof.

COROLLARY 12.2
A polynomial of positive degree n over the field F has at most n distinct zeros in F.

Click here for the proof.

We can use Proposition 12.2 to do some factorizations in different fields.

EXAMPLE:
Find the factorization of x² + 1 in Z₅[x].

We found 2 be a root earlier. With a bit of experimenting another root could be found: 3. Thus,

x² + 1 = (x − 2)·(x − 3) in Z₅[x].

EXPERIMENT:
Use direct evaluation to find three roots of the polynomial

f(x) = 3 x³ + 2 x² + 2 x + 6 in Z₇[x].

For example, 0 is not a root since

In [0]:

var('x')
(3*x^3 + 2*x^2 + 2*x + 6).subs(x == 0)

is not divisible by 7. Once you have found 3 roots, write the factorization of f(x).

Here is an application of Corollary 12.2 that has many applications even using the real number field.

COROLLARY 12.3
Let F be a field, let x₀, x₁, x₂, x₃, … x_n be n + 1 distinct elements of F, and let y₀, y₁, y₂, y₃, … y_n be n + 1 values in F (not necessarily distinct). Then there is a unique polynomial ƒ(x) with degree at most n such that

f(x₀) = y₀, f(x₁) = y₁, f(x₂) = y₂, … f(x_n) = y_n.

Click here for the proof.

This corollary shows, for example, that knowing just three points of a quadratic function is sufficient to determine the quadratic function. Although this has the obvious applications to graphing polynomials, we will find in the next section some surprising real world applications when we apply this corollary to different fields.

The Sage command InterpolatingPolynomial([[x₀, y₀], [x₁, y₁], [x₂, y₂], … [x_n, y_n]], x) finds the polynomial in x derived in Corollary 4.3. For example,

In [0]:

InitDomain(0)
InterpolationPolynomial([[1,2], [2,4], [3,8]], "x")

finds the quadratic polynomial such that g(1) = 2, g(2)= 4, and g(3) = 8. Note that the first command InitDomain(0) defines the field to be rational numbers. (Yes, this command also works for other fields, such as the "complex numbers mod 3".)

EXPERIMENT:
Use Sage to find a third degree polynomial such that f(0) = 1, f(1) = 5, f(3) = 2, and f(5) = −1. Have Sage verify that this is the correct polynomial by evaluating at each of the four points.

We are now ready to define the polynomials that in many ways act as the prime numbers of number theory.

DEFINITION 12.3
A polynomial f(x) in F[x] is said to be reducible over F if f(x) has positive degree, and f(x) can be expressed as a product

f(x) = g(x)·h(x)

where both g(x) and h(x) have positive degree. If f(x) has positive degree and is not reducible, it is called irreducible.

We saw above that x² + 1 was reducible over Z₅. However, Sage will claim that this polynomial is irreducible:

In [0]:

var("x")
factor(x^2 + 1)

The reason of course is that Sage is viewing this polynomial as an element of ℚ[x], not Z₅[x]. Yet this polynomial does have a factorization if we were allowed to work with complex numbers:

In [0]:

expand( (x+I)*(x-I) )

Thus, x² + 1 is reducable over ℂ, the field of complex numbers. Thus, whether a polynomial is reducible or irreducible over F greatly depends on the field F.

It should be noted that if g(x) and h(x) both have positive degree, then g(x)·h(x) has degree at least 2. Thus, all polynomials of degree 1 must be irreducible. Constant polynomials, however, are not considered to be irreducible.

Although it can be tricky to decide whether a polynomial is reducible or irreducible, there is a way to test polynomials of low degree.

PROPOSITION 12.3
If f(x) is a polynomial of degree 2 or 3 over the field F, then f(x) is reducible over F if, and only if, f(x) has a zero in F.

Click here for the proof.

We can use this proposition to determine whether polynomials of degree less than 4 are irreducible over a finite field. Simply plug in all elements of the field, and see if any of them produce 0 in that field.

EXAMPLE:
Determine whether the polynomial

x³ + 2 x² − 3 x + 4

is reducible in Z₅.

We have:

In [0]:

var("x")
(x^3 + 2*x^2 - 3*x + 4).subs(x == 0)

In [0]:

(x^3 + 2*x^2 - 3*x + 4).subs(x == 1)

In [0]:

(x^3 + 2*x^2 - 3*x + 4).subs(x == 2)

In [0]:

(x^3 + 2*x^2 - 3*x + 4).subs(x == 3)

In [0]:

(x^3 + 2*x^2 - 3*x + 4).subs(x == 4)

One of these, namely when x was replaced by 3, produced a multiple of 5, which is equivalent to 0 in the field Z₅. Thus, this polynomial is reducible.

EXPERIMENT:
Can you determine the other factor through the division algorithm?

EXPERIMENT:
Determine whether the polynomial x² + 3 x + 4 is reducible over Z₅.

PROPOSITION 12.4
If F is a field, then all polynomials in F[x] of positive degree are either irreducible, or can be expressed as a product of irreducible polynomials.

Click here for the proof.

One last tool we have to help us find irreducible polynomials is the Greatest Common Divisor (GCD) of two polynomials. The proof of the next theorem mimicks the proof of the greatest common divisor theorem for integers (1.2).

THEOREM 12.2: The Greatest Common Divisor Theorem for Polynomials
Let F be a field, and let F[x] be the polynomials in x over the field F. Given two nonzero polynomials f(x) and g(x) in F[x], there exists a nonzero polynomial h(x) such that:

h(x) divides both f(x) and g(x).
There exist polynomials s(x) and t(x) such that

f(x)·s(x) + g(x)·t(x) = h(x).

Furthermore, the polynomial h(x) is unique except for multiplication by a constant.

Click here for the proof.

DEFINITION 12.4
Given two polynomials in F[x], the greatest common divisor is the polynomial given in the above theorem whose leading coefficient is 1.

The Sage command gcd finds the greatest common divisors of two polynomials as well as two integers. Thus, the command

In [0]:

var("x")
gcd(x^3 - 1, x^4 - 1)

shows that x − 1 divides both polynomials. Thus, there are two polynomial s(x) and t(x) such that

(x³ − 1)·s(x) + (x⁴ − 1)·t(x) = x − 1.

EXPERIMENT:
Can you find polynomials s(x) and t(x) that solve the above equation?

COROLLARY 12.4
Let F be a field, and let f(x), g(x), and h(x) be polynomials in F[x]. If f(x) is an irreducible divisor of g(x)·h(x), then either g(x) or h(x) is a multiple of f(x).

Click here for the proof.

The irreducible polynomials will play the same role in the domain F[x] as prime numbers play in the domain ℤ. The main property of integer factorizations is that every positive number greater than one can be factored uniquely into a product of primes. We would like to prove something similar polynomials in F[x], but we immediately see that an apparent complication:

2 x³ − 2 x² − 2 x − 4 = (2 x − 4)(x² + x + 1) = (x − 2)(2 x² + 2 x + 2).

Yet by the way we have defined irreducible elements,

(2 x - 4), (x² + x + 1), (x - 2) and (2 x² + 2 x + 2)

are all irreducible polynomials.

In the next section we will modify our definition of unique factorization so that the two factorizations above would be considered as equivalent.

Unique Factorization Domains

In this section we wish to determine a general definition of unique factorization that would apply not only to F[x], but for any integral domain.

DEFINITION 12.5
Let R be a commutative ring. We say that an element x in R is a unit if x has a multiplicative inverse.

In Proposition 9.7 we defined the set of invertible elements of R as R^*, and showed that they formed a group under multiplication. The units of R will play the same role as the constant polynomials do in the ring F[x]. In fact, we can model the definition of reducible and irreducible elements of a ring on the definition of irreducible polynomials in [removed]F[x].

DEFINITION 12.6
Let R be a commutative ring. If a nonzero element x in R is not a unit, and can be expressed as a product x = y·z, where neither y nor z are units, then we say that x is reducible. If a nonzero element is neither a unit nor reducible, we say it is irreducible.

Although this definition is mainly applied to integral domains, we can apply the definition to any ring with an identity.

EXAMPLE:
Consider the following ring:

In [0]:

InitRing("a","b")
DefineRing([4, 2], [[a, 0], [0, b]])
R = ListRing(); R

In [0]:

MultTable(R)

From the multiplication table, can you find an irreducible element in this ring? How many are there?

Let us consider the more familiar ring, ℤ. The only two elements with multiplicative inverses are ±1. The irreducible elements are of course the prime numbers 2, 3, 5, 7, 11, 13, …. But by this definition, the negative of a prime number is also irreducible. For example, −3 can be expressed as a product in two different ways: −1 · 3 and −3 · 1, but both of these products involve units. The dilemma of defining negative numbers as primes is that numbers can now be written as a product of primes in more than one way:

12 = 2·2·3 = 2·(−2)·(−3) = (−2)·(−2)·3.

EXPERIMENT:
By allowing negative numbers to be prime, how many ways can 30 be expressed as a product of prime numbers?

Because we now are including negative primes, we also have to redefine what is meant by unique factorization. The first step is to understand the relationship between these different factorizations.

DEFINITION 12.7
Let R be a communative ring with identity. We say that the element x is an associate of an element y if there is a unit z such that [removed]y = x·z.

Note that if x is an associate of y, then x = y·z^-1 so that y is an associate of x. Even though we saw three different factorizations of 12, these are related via associates.

DEFINITION 12.8
A ring R has unique factorization if the following two conditions are satisfied:

If x is nonzero, and is not a unit of R, then x can be written as a product of irreducible elements of R.
If x = y₁·y₂·y₃⋯y_m = z₁·z₂·z₃⋯z_n are two expressions of x as a product of irreducible elements, then m = n and there is a permutation σ ∈ S_n such that y_i and z_σ₍_i₎ are associates. In other words, each y_i is an associate of some z_j, and vice versa.

Furthermore, if R is an integral domain, then R is a unique factorization domain, abbreviated as UFD.

This definition sheds light on the polynomials which seemed to have two different factorizations. In is sense the factorizations are unique, as long as we take associates into account.

We would like to find a quick way to determine whether an integral domain is a UFD. The needed tool will be the definition of the prime elements. Although we have already defined a prime element in the integers ℤ, for a general ring we wish to define a prime element as one that satisfies a different property.

DEFINITION 12.9
A nonzero element x of a commutative ring is prime if x is not a unit, and whenever y·z is a multiple of x, then either y or z must be a multiple of x.

Although primes and irreducible elements are the same in ℤ, for many other rings they are totally different.

EXAMPLE:
Consider once again the commutative ring of order 8:

In [0]:

InitRing("a","b")
DefineRing([4,2], [[a, 0], [0, b]])
MultTable(ListRing())

Show that even though a is not irreducible, a is prime in this ring.

We need to show that whenever y·z is a multiple of a, then either y or z is a multiple of a. Another way of saying this is that whenever y or z are not multiples of a, then y·z is not a multiple of a. The multiples of a are {0, a, 2a, −a}, so the non-multiples of a are {b, a + b, 2a + b, −a + b}. The above table shows that multiplication is closed under this set, so a is prime, even though it is not irreduciable.

EXPERIMENT:
Find all of the prime elements of this ring. Show that any nonzero element is either a unit or can be expressed as a product of primes.

Although in this ring we found prime elements that was not irreducible, we can show that this can only happen when the ring has zero divisors.

LEMMA 12.1
If K is an integral domain, and x is a prime element of K, then x is irreducible.

Click here for the proof.

Even though a prime element is irreducible, it is not true that an irreducible element is prime! Consider for example the numbers of the form x + y√−5 where x and y are integers. This ring is refered to as ℤ[√−5]. To determine the irreducible elements of this ring, let us define the following function on ℤ[√−5]:

N(x + y√−5) = (x + y√−5)(x − y√−5) = x² + 5 y².

Notice that N(z) is the product of the number z with its complex conjugate. The full signifigence of this function will be revealed later in this chapter. For now we can observe that if a and b are in ℤ[√−5], N(a·b) = N(a)·N(b). Hence, N(a) is a group homomorphism from the multiplicative group of ℤ[√−5] to ℤ⁺. This homomorphism will help us to determine the irreducible elements of ℤ[√−5].

Let us begin by finding the units of ℤ[√−5]. If a = x + y√−5 is invertible, then N(a) must be invertible. Hence x² + 5 y² = 1. The only integer solution to this equation is when y = 0 and x = ±1. Thus, ±1 are the only units of this ring.

Next, let us find an irreducible element. Since N(2) = 4, the only way a product of non-units a and b could be equal 4 is if both N(a) and N(b) were equal to 2. But the equation x² + 5 y² = 2 clearly has no integer solutions. Thus, 2 is an irreducible element in this ring. By the same reasoning, N(3) = 9, and x² + 5 y² = 3 has no solutions, so 3 is irreducible.

However, neither 2 nor 3 is a prime element of this ring! Consider the product

(1 + √−5)(1 − √−5) = 1 + 5 = 6.

This product is a multiple of 2 and 3, but neither factor is a multiple of 2 or 3. Thus, 2 and 3 are not prime in this ring.

This example shows a ring that is not a unique factorization domain. We have seen two ways of factoring the number 6, and the two factorizations are not equivalent in terms of associates.

The ring ℤ[√−5] can be generalized to produce similar rings, some of which are UFD's, and some are not.

DEFINITION 12.10
Let n be an integer that is not divisible by the square of any integer other than 1. Then the ring ℤ[√n] is called a quadratic domain.

We have already worked with some examples of quadratic domains. For example, we found two possible ways to order the ring ℤ[√2], using ring homomorphisms. In §12.4, we will generalize the N function to determine whether many of these quadratic domains are UFD's.

The fact that neither 2 nor 3 was prime in the quadratic domain ℤ[√−5] is a clue as to why this ring is not a UFD.

PROPOSITION 12.5
An integral domain is a UFD if, and only if, all nonzero, non-units can be written as a product of primes.

Click here for the proof.

This proposition will help us greatly in determining whether an integral domain is a UFD. We usually will proceed in two steps: proving that any element can be written as a product of irreducible elements, and then proving that any irreducible element is prime.

COROLLARY 12.5
If F is a field, then the ring F[x] is a UFD.

Click here for the proof.

Although this corollary proves that polynomials over the rational numbers have a unique factorization, we still have not proven that ℤ[x], the polynomials over the integers, is a unique factorization domain. Corollary 12.5 will not help us, since ℤ is not a field. Yet is seems plausible that we could prove that ℤ[x] is a UFD, merely by using the fact that ℚ[x] is a UFD. In the process, let us prove that R[x] is a UFD whenever R is a UFD. First, we will need to prove a few lemmas. This next lemma, commonly refered to as Gauss' lemma, uses the formula for the product of two polynomials.

LEMMA 12.2: Gauss' Lemma
If R is an integral domain, then a prime element of R is also a prime element of R[x].

Click here for the proof.

With Gauss' lemma (12.2), we can see that whenever a product of several polynomials in R[x] is divisible by a p, a prime number of R, then one of those polynomials must have been divisible by p. We can use induction to extend this argument to when p any element of R.

LEMMA 12.3
Let R be a unique factorization domain, and let

g₁(x), g₂(x), g₃(x), … g_n(x)

be polynomials in R[x] that are not divisible by any prime element of R. Let f(x) be a polynomial in R[x], and let c and d be two elements in R such that

c·f(x) = d·g₁(x)·g₂(x)·g₃(x) ⋯ g_n(x).

Then d is divisible by c in R.

Click here for the proof.

The next step in proving that R[x] is a UFD is to find the irreducible elements of R[x]. If there is a field F that contains R, we can use the irreducible elements of F[x] to find the irreducible elements of R[x].

LEMMA 12.4
Let R be a unique factorization domain, and let F be a field containing R. Then if f(x) is a polynomial in R[x] that is irreducible in F[x], then f(x) can be writen

f(x) = c·g(x),

where c is an element of R, and g(x) is irreducible in R[x].

Click here for the proof.

Although this lemma refers to some field F which contains R, there is a natural field to use—the field of quotients in R. We can use this field to show that, in fact, the irreducible elements of R which we found in Lemma 12.4 are in fact prime elements of R[x].

LEMMA 12.5
Let R be a unique factorization domain, and let F be the field of quotients for R. Then if g(x) is irreducible over R[x] and F[x], then g(x) is prime in R[x].

Click here for the proof.

At this point all of the major battles have been fought. All that is left to do is put the pieces together to show that R[x] is UFD.

THEOREM 12.3: The Unique Factorization Domain Theorem
R[x] is a unique factorization domain if, and only if, R is a unique factorization domain.

Click here for the proof.

Not only does this theorem determine when we can consider polynomial factorization to be unique, but this theorem also applies to factoring polynomials in more than one variable.

Since R[x] is an integral domain, we can consider another variable y, and consider the polynomial ring R[x][y]. A typical element of R[x][y] would be

c₀(x) + c₁(x) y + c₂(x) y² + c₃(x) y³ + ⋯ + c_n(x)yⁿ,

where each c_i(x) is a polynomial in R[x]. If each c_i(x) is written

c_i(x) = d_{0 i} + d_{1 i} x + d_{2 i} x² + d_{3 i} x³ + ⋯,

we find that the polynomial in R[x][y] could be written

d_{0 0} + d_{1 0} x + d_{0 1} y + d_{2 0} x² + d_{1 1} x·y + d_{0 2} y² + ⋯.

If we make the convention that x·y = y·x, then it is easy to see that R[x][y] = R[y][x].

DEFINITION 12.11
We will denote the polynomial ring of two variables by R[x,y] = R[x][y]. The variables x and y are called indeterminates. Likewise, we denote the polynomial ring of n indeterminates by

R[x₁, x₂, x₃, … x_n].

COROLLARY 12.6
Let R be a unique factorization domain and let x₁, x₂, x₃, … x_n be indeterminates over R. Then R[x₁, x₂, x₃, … x_n] is a unique factorization domain.

Click here for the proof.

Polynomials in several varibles are of considerable importance in geometry, since curves and surfaces are described by equations in several variables. Although Sage's Factor command will be able to factor polynomials in many variables, its ability is limited to when R is either ℤ or ℚ. For example, Sage can factor

In [0]:

var("x y")
factor(x^3*y^2 + x^2*y - x*y^2 - 2*x + y)

over the integers, but cannot factor this over any other ring, even a finite field. The reason is simply a lack of efficient algorithms for factoring polynomials in more than one variable.

EXPERIMENT:
Just to demonstrate the difficulty of factoring a polynomial with more than one variable, try to factor the polynomial

x⁵ − x⁴ y + 2 x y² − 4 x − 4 y

by hand. One would think that having 2 variables would give more clues to the factorization, but in fact the factorization becomes tricky. If you totally give up, have Sage give you the factorization.

Sage's ability to factor such polynomials will later come in very handy, since the problem of factoring a polynomial over an unusual ring is often equivalant to the problem of factoring a polynomial of several variables over ℤ.

Principal Ideal Domains

Although we have found that polynomial rings created from unique factorization domains produce more unique factorization domains, there still is the question of how to tell whether a given ring is a unique factorization domain. The answer lies in the ideals of the ring. In this section we will explore the interesting interconnection between the ideals of a ring, and the prime and irreducible elements of the ring.

We begin by recalling that many ideals can be generated with only one element. In fact, many rings, such as the integers ℤ, are such that every ideal is generated by only one element. We called such rings principal ideal rings, or PIRs. (When the ring is also a domain, we call it a principal ideal domain, or PID.) In fact, PIDs are so common that it is somewhat tricky to find an example of an integral domain that is not a PID.

EXAMPLE:
Consider the ring R = ℤ[x,y]. We saw by Corollary 12.6 that this is a UFD. We would now like to show that this is not a PID. Consider the ideal of elements without a constant term. This ideal can be expressed as ⟨{x, y}⟩, that is, the ideal generated by x and y. But since both x and y are in this ideal, we cannot express this ideal as the multiples of a single polynomial. Thus, this ideal is not a principal ideal, so ℤ[x,y] is not a PID, even though it is a UFD.

The following definition sheds light on the connection between ideals and unique factorization domains.

DEFINITION 12.12
Let R be a commutative ring, and let P be a nontrivial ideal of R. (Thus, P is neither {0} nor R.) We say that P is a prime ideal if, whenever x and y are in R, and x·y is in P, then either x or y is in P.

When we first defined a prime element of a ring, we were careful to mention that the ring did not have to be an integral domain. By defining prime elements for all commutative rings, we open the door to showing a connection between prime ideals and prime elements.

PROPOSITION 12.6
Let R be a commutative unity ring. Then p is a prime element of R if, and only if, the principal ideal ⟨p⟩ is a prime ideal.

Click here for the proof.

Although this proposition refers to principal ideals, it is certainly possible for an ideal to be a prime ideal without being even a principal ideal.

EXAMPLE:
Show that the ideal of the previous example is a prime ideal.

Note that we can characterize the ideal ⟨{x, y}⟩ as

⟨{x, y}⟩ = {ƒ(x, y) ∈ ℤ[x,y] | ƒ(0,0) = 0}.

Thus, if f(x, y)·g(x, y) is in the ideal ⟨{x, y}⟩, we have f(0,0)·g(0,0) = 0, so either f(0,0) = 0 or g(0,0) = 0. Therefore, either f(x,y) or g(x,y) is in ⟨{x, y}⟩, so ⟨{x, y}⟩ is a prime ideal, even though it is not a principal ideal.

Although Proposition 12.6 gives us a test for determining whether an element is prime, to impliment this we need a test to see whether an ideal is a prime ideal. The next proposition does the trick.

PROPOSITION 12.7
Let R be a commutative unity ring, and let P be a non-trival ideal of R. Then P is a prime ideal if, and only if, the quotient ring R/P has no zero divisors.

Click here for the proof.

EXAMPLE:
Determine whether 2 a + b is a prime element of the following familar commutitive ring:

In [0]:

InitRing("a","b")
DefineRing([4, 2], [[a, 0], [0, b]])
R = ListRing(); R

We already determined that the element 2 a + b was irreducible in this ring. To determine whether 2 a + b is prime, we compute the quotient ring R/⟨2a + b⟩.

First, we find the principal ideal generated by 2a + b:

In [0]:

S = Ideal(R, 2*a + b); S

This forms a nontrivial ideal, so we can now consider the quotent ring.

In [0]:

Q = Coset(R, S); Q

The quotient group has only two elements, so there is a good chance that this has no zero divisors. We can double check by looking at the multiplication table.

In [0]:

QuotientRing = true
MultTable(Q)

Thus, the quotient is isomorphic to Z₂. By Proposition 12.7, 2a + b is prime.

EXPERIMENT:
Try the above procedure on the other 6 nonzero elements of R. Which elements are prime?

Although we can clearly use Sage along with Proposition 12.7 to find the prime elements of any finite ring, we are mainly interested in finding the prime elements of an infinite ring. Sage can still help us out, since the quotient ring R/⟨p⟩ will usually be finite.

EXAMPLE:
Determine whether 3 is prime in the ring ℤ[√−5].

We saw in the last section that 3 was an irreducible element. Let us use Sage to see if 3 is a prime number in this ring. We first construct the ring ℤ[√−5] by letting a = √−5.

In [0]:

InitDomain(0)
AddFieldVar("a")
Define(a^2, -5)

We can now try to factor in this new ring

In [0]:

factor(3 + 2*a)

So we see that 3 + 2√−5 is prime in this domain. What happens if we try to factor 3?

In [0]:

factor(3 + 0*a)

We get an error message, complaining about a non-principal ideal. Thus, we see that 3 is not prime in ℤ[√−5], even though it is irreducible.

To really see what is going on, let us construct the ring ℤ[√−5]/⟨3⟩. We have to plan ahead to see that this ring has nine elements. We can let e represent the identity element 1 + ⟨3⟩, and a represent √−5 + ⟨3⟩. Both of these will have additive order of 3, so we can define the ring by

In [0]:

InitRing("e","a")
DefineRing([3, 3], [[e,a],[a,-5*a]])
R = ListRing(); R

In [0]:

MultTable(R)

We see that this ring has zero divisors, so by Proposition 12.7, 3 is not prime in this domain, even though it is irreducible.

EXPERIMENT:
Use the same procedures to show that 2 is not a prime element of ℤ[√−5]. Is 7 a prime element in this ring? How about 11?

We have seen that Proposition 12.7 is a useful way of determining whether an element is prime. Let us use this proposition to show that in a principal ideal domain, irreducible elements are also prime elements. This amounts to showing that R/⟨p⟩ has no zero divisors whenever p is irreducible. However, we can actually prove more, which will be very useful later on.

LEMMA 12.6
Let R be a principal ideal domain, and let p be an irreducible element of R. Then the quotient ring R/⟨p⟩ is a field.

Click here for the proof.

From this lemma, it is easy to see that an irreducible element of a PID must also be a prime element. Thus, we are on our way to showing that a PID is a unique factorization domain. By Proposition 12.5, we only need to show that every non-invertible element can be expressed as a product of irreducible factors. In order to eliminate the posibility of an "infinite chain" of irreducible elements, each one dividing the previous, we will use the following lemma.

LEMMA 12.7
Let R be a principal ideal ring. If there is an infinite sequence of larger and larger ideals of R satisfying

I₁ ⊆ I₂ ⊆ I₂ ⊆ ⋯ ⊆ I_n ⊆ I_n+1 ⊆ ⋯,

then there exists an integer m such that I_n = I_m for all n > m.

Click here for the proof.

We now have all we need to show that a PID is in fact a UFD.

THEOREM 12.4:The Principal Ideal Domain Theorem
Every principal ideal domain is a unique factorization domain.

Click here for the proof.

This theorem reveals the most important use of principal ideal domains—it enables us to find unique factorization domains. For example, ℤ was proven to be a PID from Proposition 10.3, so we now can see that ℤ is a UFD, as result that was proven in §0.1.

It should be noted that not all unique factorization domains are PIDs—in fact we discovered that ℤ[x,y] is not a PID, even though it is a UFD. However, many of the important unique factorization domains are also principal ideal domains. In the next section we will find many more examples of principal ideal domains.

Euclidean Domains

We have already seen the importance of principal ideal domains to determine whether a ring is a unique factorization domain. However, we still have the problem of determining whether a given integral domain is a principal ideal domain. If we have a tool such as the division algorithm, this can usually be done quite easily. For example, the integers ℤ was proven to be a PID from Proposition 10.3.

EXAMPLE:
Show that F[x] is a PID for any field F.

We examine what the ideals could be. If I is a nontrivial ideal of F[x], we can find a nonzero element f(x) in I with the lowest degree. If g(x) is also in I, then by the division algorithm

g(x) = f(x)·q(x) + r(x),

with the degree of r(x) less then f(x). But r(x) would also be in I, and since f(x) has least degree of all the nonzero elements in I, we must have r(x) = 0. Therefore all elements of I are multiples of f(x), so I = ⟨f(x)⟩.

Rather than making this a formal proposition, we want to study this example, since we can prove that many different domains are PIDs the same way. There were two keys to the proof that F[x] was a PID: the fact that every polynomial had a degree, and the division algorithm. Whenever we have an integral domain that has a property like a division algorithm, there is a good chance that we can use this division algorithm to prove that the ring is a PID. Let us formulate what we mean by a "division algorithm."

DEFINITION 12.13:
An integral domain R is called a Euclidean domain if there is a function μ(x) defined on the nonzero elements of R such that the following three properties hold:

μ(x) is a non-negative integer for every nonzero x in R.
Whenever both x and y are nonzero, μ(x·y) ≥ μ(x).
For and x and y in R, with y nonzero, there exist elements q and r in R such that

x = q·y + r,

where either r = 0 or μ(r) < μ(y).

The function μ(x) is called the Euclidean valuation on R.

EXAMPLE:
Since this definition was modeled after the ring F[x], it is expected that F[x] is a Euclidean domain. The function μ(f(x)) would be the degree of the polynomial f(x). Properties 1 and 2 come from the definition of the degree, and Lemma 11.1. Property 3 we observed in the division algorithm theorem (12.1). Thus, F[x] is a Euclidean domain whenever F is a field.

However, there are many other examples of Euclidean domains. Consider the set of integers, ℤ. We can use the absolute value for the valuation: μ(x) = |x|. Clearly properties 1 and 2 hold, and the third property comes from modular arithmetic. Thus, ℤ is also a Euclidean domain.

Whenever we have a Euclidean domain, we can prove that the domain is a PID, using the exact same argument as we did for F[x].

THEOREM 12.5:The Euclidian Domain Theorem
Every Euclidean domain is a principal ideal domain.

Click here for the proof.

We started this section by showing that F[x] is a principal ideal ring whenever F is a field, but let us formally make this a corollary of the Euclidean domain theorem.

COROLLARY 12.7
Let F be a field. Then the ring of polynomials F[x] is a principal ideal domain.

Click here for the proof.

The only problem with this definition of the Euclidean domain is that it gives no help in determining what the valuation function μ(x) should be. In fact, there may be many possible valuation functions for a given integral domain. (See Problem 1 for an alternative definition of a Euclidean domain that does not involve a valuation function.)

For the remainder of this chapter, we will consider the problem of determining whether some quadratic domains are Euclidean domains. This class of domains will help us to see some general techniques for finding a valuation function for a domain. We have already seen that ℤ[√−5] is not a UFD, so this clearly is not a Euclidean domain.

We saw before that ℤ[√2] had two automorphisms, and in general quadratic domain ℤ[√n] will always have two automorphisms, the identity mapping, and the automorphism

ƒ(x + y√n) = x − y √n.

We define the function N(a) as the product of the two automorphisms:

N(x + y√n) = (x + y√n)·(x − y√n) = x² − n·y².

It is interesting that N(a) is always an integer.

At first glance it may be difficult to see what N(a) has to do with the Euclidean domains. Our goal is to construct a valuation function from N(a). We first need to verify some elementary properties of this function. In the process, we will notice these properties are still valid if we extend N(a) to be defined on ℚ[√n].

LEMMA 12.8
Let ℤ[√n] be a quadratic domain, and let N(x + y√n) = x² − n·y². Then for the rings ℤ[√n] and ℚ[√n],

N(a) = 0 if, and only if, a = 0.
N(a·b) = N(a)·N(b)
N(±1) = 1.

Click here for the proof.

We can use the N(a) function to prove that ℚ[√n] is a field.

COROLLARY 12.8
Let n be an integer that is not divisible by the square of any integer greater than 1. Then the ring ℚ[√n] is a field.

Click here for the proof.

Using the three properties of the norm function N(a), we are able to determine at least some of the irreducible elements of the ring K. This reveals the connection between the norm, and the unique factorization properties of the ring.

PROPOSITION 12.8
Let ℤ[√n] be a quadratic domain, and let N(x + y√n) = x² − n·y². Then

N(a) = ±1 if, and only if, a is a unit in ℤ[√n].
If N(a) is a prime number in ℤ, then a is an irreducible element of ℤ[√n].

Click here for the proof.

We can now use the Euclidian valuation function μ(x) = |N(x)| to prove the following.

PROPOSITION 12.9
The integral domains ℤ[√−2], ℤ[√−1], ℤ[√2], and ℤ[√3] are Euclidian domains.

Click here for the proof.

One of these four domains has special applications. The ring ℤ[√−1] = ℤ[i] is called the domain of Gaussian integers. Sage's factor command can find the prime factorization over the Gaussian integers by first defining the field of complex rational numbers.

In [0]:

InitDomain(0)
AddFieldVar("i")
Define(i^2, -1)

For example, we can now factor the number 5 as follows:

In [0]:

factor(5 + 0*i)

This reveals that 5 = (−i − 2)·(i − 2). These two factors are apparently both prime.

EXPERIMENT:
Replace the 5 with different numbers to see the prime factorization over this new domain. Try this with complex numbers as well. See if you can find a pattern on which Gaussian integers are prime.

By investigating further the divisibility properties of ℤ[i], one can prove the classic "two squares theorem" of Fermat: Every prime number of the form is the sum of two squares. (See Problem 10 from §13.2.) It is interesting that the study of domains other than the familiar integers can yield new information about the integers.

We can also explore factorizations in the other Euclidean domains found in Proposition 12.9. For example, the domain ℤ[√−2] can be set up with the commands:

In [0]:

InitDomain(0)
AddFieldVar("a")
Define(a^2, -2)

Then we can factor numbers such as

In [0]:

factor(3 + 0*a)

So 3 is not prime in this domain!

EXPERIMENT:

See what other primes in the ordinary sence factor in this new domain.

The domain ℤ[√2] is even stranger, for there are an infinite number of units.

In [0]:

InitDomain(0)
AddFieldVar("a")
Define(a^2, 2)

Although a is not a unit, (it is prime), we find that 1 + a is.

In [0]:

1/(1+a)

This means that

In [0]:

(1+a)^2

In [0]:

(1+a)^3

In [0]:

(1+a)^4

and so on produces an infinite number of units.

In [0]:

factor(3 + 0*a)

This time, 3 is prime in the domain, but 2 is not, since 2 = a².

EXPERIMENT:

See what other primes in the ordinary sence are still prime in the new domain.

Proofs:

Proof of Theorem 12.1:

We begin by showing that q(x) and r(x) exist, and then prove that they are unique. If f(x) = 0, or if the degree of f(x) is less than the degree of g(x), we can simply let q(x) = 0, and r(x) = f(x). So we may suppose that the degree of f(x) is at least as large as the degree of g(x). Let n be the degree of f(x), and let m be the degree of g(x).

If n = m = 0, then f(x) and g(x) are both nonzero constants in the field F, so we may pick q(x) to be the constant polynomial f·g^-1, and pick r(x) = 0. Thus, we can find a suitable q(x) and r(x) when n = 0.

Now let us proceed by induction on n. That is, we will assume that we can find a suitable q(x) and r(x) whenever the degree of f(x) is less than n. Let

f(x) = a_n xⁿ + a_n−1 xⁿ⁻¹ + ⋯ + a₀,

and

g(x) = b_m x^m + b_m−1 x^m−1 + ⋯ + b₀.

Since n is at least as large as m, we can consider the polynomial

p(x) = a_n b_m^-1 x^n−m

of degree n − m. By Lemma 11.1, p(x)·g(x) has degree n, and in fact, since

p(x)·g(x) = a_n xⁿ + a_n b_m^-1b_m−1 xⁿ⁻¹ + ⋯ + a_n b_m^-1b₀ x^n−m

the coefficient of the xⁿ term would be a_n. Thus, f(x) − p(x)·g(x) is of degree less than n. So by the induction hypothesis, there exist polynomials z(x) and r(x) such that

f(x) − p(x)·g(x) = z(x)·g(x) + r(x)

with the degree of r(x) less than the degree of g(x). Thus,

f(x) = (p(x) + z(x))·g(x) + r(x).

By letting q(x) = p(x) + z(x), we have proved that suitable q(x) and r(x) exist.

Next, let us prove that q(x) and r(x) are unique. Suppose that there is a second pair q(x) and r(x) such that f(x) = q(x)·g(x) + r(x). Then

q(x)·g(x) + r(x) = q(x)·g(x) + r(x),

(q(x) − q(x))·g(x) = r(x) − r(x).

The left hand side is either 0 (when q(x) = q(x) ), or has degree at least m, since g(x) is of degree m. The right hand side is either 0, or has a degree less than m. This is a contradiction unless both sides of the equation are 0. Thus, q(x) = q(x) and r(x) = r(x), and the uniqueness has been proven.

f₀(x) =	(x − x₁)·(x − x₂)·(x − x₃) ⋯ (x − x_n)

	(x₀ − x₁)·(x₀ − x₂)·(x₀ − x₃) ⋯ (x₀ − x_n)

	∞
I =	∪	I_n
	n = 1

Factorization of Polynomials

Unique Factorization Domains

Principal Ideal Domains

Euclidean Domains

Proofs:

Sage Interactive Problems