Factorization

Factoring and Euclidean Domain

We can extend the notion of factorization to rings (integral domains) other than :

Factorization & Division in Integral Domain

Suppose is an integral domain. We have the following definitions:

• is a unit if is invertible in .
• divides if there exists such that .
• is a proper divisor of if divides , say , with neither nor units.
• and are associates if divides and divides . i.e. for some unit .
• is irreducible if is not a unit and it has no proper divisors, i.e. its only divisors are units and associates.
• is prime if is not a unit and whenever divides , then divides or divides .

Size Function

A size function on an integral domain can be any function whose domain is the set of nonzero elements of and whose range is the set of nonnegative integers.

e.g. A multiplicative size function is especially useful, because it allows us to convert the factorization problem in an arbitrary integral domain to a factorization problem in (even ). For example, consider . We can define a size function on such that , where denotes the complex modulus. Thus, it satisfieswhich is multiplicative. Let’s consider , whose size is . As can only be factored into in , but there is neither size nor size element in , hence we can conclude that is irreducible in .

Euclidean Domain

An integral domain is an Euclidean domain if there exists a size function on such that division with remainder is possible: for all with , there exist such that with or .

e.g.

• is an Euclidean domain with size function be the absolute value.
• A polynomial ring over a field is an Euclidean domain with size function be the degree of the polynomial. But for a non field ring , will not make a Euclidean domain. A simple example is in , cannot divide with remainder, because in . Indeed, is not even a PID.
• The ring of Gaussian integers (complex numbers with both real and imaginary parts being integers) is an Euclidean domain with size function being the complex norm.
• In fact, if , then the complex norm will make a Euclidean domain. This is because if we want to divide by , we can look at the complex number . If it is in , then we are done, and the remainder . Otherwise, we can pick the nearest integer to in as , and let their difference be , then we have , so . Note that , because by our assumption, , so . Hence , and we can take as the remainder. Geometrically, the condition means that every point in the parallelogram (or rectangle) of side lengths and in the complex plane is within distance less than from some vertex.

Proposition

A Euclidean domain is a principal ideal domain.

Proof We mimic the proof that is a principle ideal domain once again. Let be an Euclidean domain with size function . Let be a non trivial ideal. Pick such that is minimal. We claim . For any , by the remainder theorem, we have for some with . Since , it follows that . As is minimal, we must have . Therefore .

Greatest Common Divisor & Relatively Prime

Let be elements of an integral domain . The greatest common divisor of and is an element such that:

• divides both and .
• If divides both and , then divides .

We say and are relatively prime if their greatest common divisor is a unit.

GCD may not exist

There will often be a common divisor that is maximal, meaning that and have no proper divisors in common. However, this element may fail to satisfy the second property. For instance in the ring , the elements and are divisible by and . These are maximal elements among common divisors, but neither one divides the other.

Proposition

Any two greatest common divisors of and are associates.

Proof It is straightforward by the second property of the greatest common divisor.

Proposition

Let be a principle ideal domain, and let and be elements of , which are not both zero. Then whatever element generates the ideal is a greatest common divisor of and . And there are elements such that .

Proof Let be an element that generates the ideal. Then divides both and . Let be another common divisor of and . Then , and so contains , so divides . Therefore is a greatest common divisor of and . Moreover, existence of such that follows from the fact that .

Unique Factorization Domains

Unique Factorization Domain

An integral domain is a unique factorization domain if it has the following properties:

• Factoring terminates.
• The irreducible factorization of an element is unique, up to order and associates.

e.g. Every field is vacuously a unique factorization domain. is not a unique factorization domain, because .

Proposition

Let be an integral domain, then the following conditions are equivalent:

• Factoring terminates.
• does not contain an infinitely strictly increasing chain of principle ideals.

Proposition

In any integral domain, every prime element is irreducible.

Proof Let be a prime element in an integral domain . Suppose for some . Then divides . Since is prime, divides or divides . Without loss of generality, suppose divides . Then for some . Substituting this back into , we have , and since is an integral domain, we can cancel to get . Therefore is a unit, and is irreducible.

The converse is not true

Consider . is irreducible, , but does not divide either of the factors.

Theorem

If is an integral domain, in which factoring terminates, then is a unique factorization domain if and only if every irreducible element is prime.

Proof Let be an integral domain where every irreducible element is prime. Suppose some element can be factored in two ways: Then divides , and since is prime, divides some . Without loss of generality, suppose divides . Then for some unit . Cancelling from both sides, we get Repeating this process, we can show that and the ‘s are associates of the ‘s. Conversely, suppose is a unique factorization domain. Let be an irreducible element, and suppose divides , say . Assume divides neither nor . Then and can be factored into irreducible elements, say and . Then . That are two inequivalent factorizations of , a contradiction.

e.g. Consider a non-example of the ring of continuous functions . One can factor

Corollary

Every principal ideal domain is a unique factorization domain.

Proof To show any factorization stops, it suffices to show that a infinite factorization has all tailing terms equal from some point. Note that is an ideal, hence, principle, say . Then for some , and so . Since is the union of all , we must have that is the tailing terms are all equal to , starting from .

Proposition

A unique factorization domain is a principle ideal domain if and only if all nonzero prime ideals are maximal.

Proof In a PID,

Primitive Polynomial

Suppose is a unique factorization domain. is primitive if one of (thus all) the following equivalent conditions hold:

• the greatest common divisor of its coefficients is (thus any units).
• no prime in divides all the coefficients of .
• For any prime , the canonical map evaluated at is nonzero.

If is not primitive, we can always uniquely write where is the greatest common divisor of the coefficients of and is primitive. Similarly in , we can write where is a fraction number and is primitive in .

Gauss' Lemma

The product of primitive polynomials is primitive.

Proof By the third definition of primitive polynomial, it suffices to show that is an integral domain. Note that is an integral domain, and so is .

Lemma

is primitive, suppose , such that in . Then in .

Proof Suppose , so that By the Gauss’ lemma, is primitive, since there is only a unique way to express any polynomial as a product of an element in (up to a unit) and a primitive polynomial, we must have .

Lemma

A primitive factors non-trivially in if and only if it factors non-trivially in .

Proof

Corollary

Primitive is irreducible in if and only if it is irreducible in .

Proposition

is a unique factorization domain if and only if is also a unique factorization domain.

Proof By the the theorem, it suffices to show that every irreducible element in is prime. All irreducible elements in are either a constant, or a non-constant. Since is a unique factorization domain, nothing need to be shown for constant irreducible elements. Let be a non-constant irreducible, has to be primitive and irreducible in . Suppose in , then in . So or in , and hence in by the lemma.

e.g. is a unique factorization domain, as is a unique factorization domain.

Factoring Polynomials in

By the corollary, we can tell whether a polynomial is irreducible in by checking its irreducibility in . Moreover, it is helpful to check its factorization in for some prime . Because, there are only elements to check in , and the factorization in can be lifted back to .

e.g. Consider . In , it is irreducible because So is irreducible in , thus in .

Eisenstein's Criterion

Let . Suppose there is a prime such that:

• divides all except .
• does not divide .

Then is irreducible in .

In fact, the Eisenstein’s criterion holds for any unique factorization domain, not just . We shall prove it in the following.

Generalized Eisenstein's Criterion

Let , where is a unique factorization domain. Suppose there is a prime such that:

• divides all except .
• does not divide .

Then is irreducible in .

Proof Up to contradiction, suppose in , where , and . The hypothesis implies that becomes in , so in , has to be and has to be , which means divides all , except and . Therefore, divides , which is a contradiction.

Lemma

Let , where is an integral domain. Then is irreducible if and only if is irreducible for all .

Proof If , then . Conversely, if , then , if we let .

Theorem

The cyclotomic polynomial is irreducible in for any prime .

Proof We know that , substituting and we obtain, we cancel , and get for which the Eisenstein’s criterion applies with as the prime. Hence, is irreducible in .

Gauss Primes

We have seen that the ring of Gauss integers is a Euclidean domain. In this section we describe the prime elements in , and their relation to prime elements in .

Lemma

The following are true in :

• A Gauss integer that is a real is an intger.
• An integer divides a Gauss integer in if an only if divides both and in .

Lemma

Let be an prime integer, the followings are equivalent:

• is a prime in .
• the quotient is a field.
• is an irreducible element in .