2.4 Factorization

Fundamental concepts: Let B be a commutative ring. If +a, b, c are elements of R and

ab = c (1),

then a and b are said to be factors of c and c is said to be divisible by a and. b. Whereas in a field every element is divisible by every element other than zero, there is no corresponding theorem for rings. As certain rings - for example, the ring of the integral numbers, and the rings R[x] — have an important role in mathematics, it is necessary to consider the mutual divisibility of elements of certain classes of rings which are not fields.

Let D be an integral domain. If every element of D is divisible in D by a particular element, say e, then 1 is divisible by e, and therefore e^-1 belongs to D. If on the other hand, e and e^-1 belong to D, then for every a of D the elements ae^-1 and ae belong to D; hence every element a of D is divisible by e and e^-1. Thus, the elements which are factors of every element of D are exactly those elements of which an inverse element exists in D. The unit element 1, for instance, has this property, whence these elements are called unities of D. If e₁ and e₂ are unities, then the same is true e₁e₂ and e₁e₂^-1. Thus the unities in D form a multiplicative commutative group.

Certain examples:

1. Let D be the ring of the integral numbers, then + 1 and -1 are the only unities.
2. Let F be a field, then every element different from zero is a unity.
3. The unities of F[x] are the polynomials of degree 0 (i.e., the elements of F, with the exception of 0).

Let a and b be two elements of D for which a:b = e is a unity of D; then a and b are said to be associated. This association of elements satisfies the laws of reflexivity, symmetry and transitivity; thus D is partitioned into classes of associated elements (associates).

Every element of D is divisible by its associates and by the unities. A non-zero and non-unity element which is not divisible by any other element than its associates and unities is said to be a prime-element. For example, in the ring of the integral numbers, an element is associated to itself and to its negative; the prime-numbers taken with positive or negative sign are the prime-elements. In an arbitrary field, all the non-zero elements are unities, but there might be elements which are neither zero nor unities and are non-divisible by any prime-element provided the domain D is suitably chosen. For example, consider the numbers

(2)

for n = 0, 1, 2, ··· and a₀, a₁, ··· - integral numbers. The numbers (2) form an integral domain D with the unities 1 and -1, the prime-elements being the odd prime numbers with positive or negative sign. The number 2 is not a unity and is not divisible by any prime-element of D.

If an element can be represented as a product of unities and prime-elements, it is said to be factorizable, the representation itself is called a factorization. Obviously, a prime-element is always factorizable. If an element a is non-factorizable, it is neither a unity nor a prime, and it is divisible by an element b which is not associated to a and is itself non-factorizable. Two factorizations of an element will not be considered to differ, if there is a (1,1)-correspondence between the prime-elements, corresponding prime-elements being associated. If all the factorizations of an element a are equal in this sense, then the factorization of a is said to be unique. If the factorization of every element which is neither zero nor a unity is unique, then one says that the factorization in D is unique. Thus the factorization in a field is unique.

Exercises:

1. Construct an integral domain D which is not a field, but does not have a no-prime-element.
(2) Investigate the extension of the notions explained here to rings which are not integral domains.

2.4.2 Domains with factorizable elements

Theorem: Let D be an integral domain and let there correspond to every element a ¹ 0 of D an integral positive number N(a) - the norm - such that

N(ab) ³ N(a), (1)

where the equality applies if and only if b is a unity; then every element ¹ 0 in D is factorizable.

Proof: If a is a product of non-unity elements,

a = a₁ ··· a_m

then

Again, if a is not factorizable, it is the product of two non-unities, say a=a₁b₁ of which at least one, say b₁, is not factorizable, whence

a = a₁b₁ = a₁a₂b₂ = ··· a₁a₂ ··· a_nb_n,

where n can be chosen > N(a) and none of the factors is a unity. But by (2), N(a) ³ n + 1 which is a contradiction, whence follows the theorem.

Examples:

1. Let D be the domain of the integral numbers and N(a) be the absolute value: N(a) = | a|. Then N(a) satisfies (1). Hence the integral numbers are factorizable.
2. Let D be the set of the numbers

a + bÖ(-6), (3)

where a , b take all the integral values; then D is an integral domain.

Let

N(a + bÖ(-6)) = a ² + 6b ² = (a + bÖ(-6))(a - bÖ(-6) (4)

then

N(ab) = N(a) N(b) (5)

and for a ¹ 0, N(a) > 0 is an integral number.

If N(a + bÖ(-6)) = 1, then (a - bÖ(-6)) = 1: (a + bÖ(-6)), whence a+bÖ(-6) is a unity. Therefore N(ab) = N(a) N(b) > N(a) if b is not a unity. On the other hand, if e is a unity,

1 = N(1) = N(ee^-1) = N(e)N(e^-1),

and therefore N(e) = 1 as 1 has no positive factor other than 1. Finally, N(ae)=N(a)N(e)=N(a), whence the norm (4) satisfies Condition (1). In this integral domain, factorization is not unique, since

6 = 2·3 = - [Ö(-6)]².

We have to prove that 2, 3 and Ö(-6) are prime elements in D. N(2) = 4, N(3)=9, N(Ö(-6)) = 6. If one of the 3 elements were not prime, there must be elements of which the norm is equal to 2 or 3. If a is an integral number

a ² º 0 or 1 (mod 3), (6)

according to a being divisible by 3 or not. Again, let N(a + bÖ(-6)) = 2, then a² + 6b ² = 2, a ² º 2 (mod, 3) in contradiction to (6). Let N(a + bÖ(-6)) = 3, then a² + 6b ² = 3, whence a is divisible by 3, say a = 3k, multiplication by 2 : 3, yieldst 6k ² + 4b² = 2, whence (2b ²) º 2 (mod, 3) contrary to (6). Thus 2, 3 and Ö(-6) are prime elements; so 6 can be factorized in two different ways.

2.4.3 Unique factorization: One frequently uses

Criterion for uniqueness of factorization: Let D be an integral domain in which every element ¹ 0 is factorizable. The necessary and sufficient condition for the uniqueness of factorization is that no product ab can be divisible by a prime-element p unless a factor a or b is divisible by p.

Proof: 1. Let the factorization be unique in D. One finds the factorization of c=ab by combining the factorizations of a and b. On the other hand, c = d p, and one gets the factorization of c combining the factorizations of d and the prime-element p. From the uniqueness of the factorization, it follows that an associate of p occurs among the prime-factors of a or of b. Hence a or b is divisible by p.

2. Let the above condition for products hold; it can then be proved by mathematical induction that, if a a₁ ··· a_n is divisible by p, at least one of the factors is divisible by p. Of course, the proposition holds for n = 1; let it be true for n < m. If a (a₁ ··· a_n) is divisible by p, and a is not divisible by p, the product in brackets is divisible by p, and therefore one of the factors is divisible by p. Now, let c be factorized c = p₁ ··· p_n, and c be divisible by a prime-element p, then at least one of the prime-elements p is divisible by p and therefore associated with p. Suppose now that there exist in D elements, which are not uniquely factorizable, and let r be the minimum number of prime-factors (which are not necessarily all different) such that b = q₁ ··· q_n admits a different factorization b = p₁ ··· p_s (where s = or ¹ r). Obviously r > 1. As b is divisible by p_s, one of the factors q_i is associated with p_s = u q_r, where u is a unity. Then q₁ ··· q_r-1 = p₁ ··· p_s-1u are different factorizations, contrary to the supposition that products of less than r prime-elements are uniquely factorizable. Hence follows the theorem.

If there exists in D for two elements a and b of D a common factor

(a,b) (1)

such that every common factor of a and b is a factor of ( a, b), then ( a, b) is called a highest common factor, or h.c.f. of a and b. Every element of D associated with (a, b) is also an h.c.f. of a and b. Conversely, by definition, two h.c.f.s of a and b must be divisible one by the other and are therefore associated. Hence (1) is not determined uniquely, but only up to a unity-factor, provided that an h.c.f. exists at all.

Let there exist to every pair of elements of D an h.c.f., then every common factor of 3 elements, say a, b, c is a common factor of (a, b) and c, and therefore a factor of d = ((a, b), c). On the other hand, d is a common factor of a, b and c. Thus, there exists an h.c.f. to every triplet of elements of D. Obviously, this h.c.f. is uniquely determined up to a unity-factor. By repeating this procedure, one obtains easily

Theorem I: If exists to every pair of elements of D an h.c.f., then there exists to every n-tuplet a₁ ··· a_n of elements of D an h.c.f.

( a₁, ···, a_n) = (( a₁, ···, a_n-1), a_n) (2)

which is uniquely determined up to a unity factor. An element of D is a common factor of the elements of the n-tuplet if and only if it is a factor of (2).

The operation for the h.c.f. is commutative and associative; moreover, it satisfies a distributive law:

a(b,c) = (ab,ac). (3)

Let D be uniquely factorizable and

where p₁, p₂, ··· ,p_m are different prime-elements. If 0 £ s₁ £ r for j = 1, ··· , m, then for every unity e₁

is a factor of a. On the other hand, by the above criterion, a and therefore any factor of a can be divisible by such prime elements only, as they are associated to p₁, ··· ,p_m. As is not divisible by p_i, the element a and any factor of a cannot be divisible by Similarly, this is done for the other prime elements. Hence the elements (5) are the only factors of (4). Given two elements a and b of D and using the notation p⁰_j = 1, one can express both elements simultaneously by

An element (5) is therefore a common factor of a and b, if 0 £ s_j £ r_j and s_j £ t_j are true for j = 1, ··· , m. Let w_j be the smaller of the two numbers r_j and t_j, then

is an h.c.f. of a and b, whence follows

Theorem 2: If in D factorization is unique, there exists a highest common factor for every pair of elements ¹ 0.

These considerations on unique factorization agree nearly verbatim with the corresponding theory of elementary arithmetic. The only essential difference consists of the unities which occur as factors and which remain arbitrary to a certain extent. In the domain of integral numbers, there exist two unities +1 and -1, whence the prime elements occur in pairs of associated ones, while in arithmetic one tends to give preference to the positive numbers; thus, factorization becomes unique in a stricter sense. In the general case considered here, there is no way of making a similar distinction.

2.4.4 Euclidean domains: Let c₁, c₂ run over the elements of D and a, b be two particular elements; then the elements

c₁ a+ c₂b (1)

form a commutative ring which with every element contains also its multiples, and especially its associates. Every element (1) is divisible by every common factor of a and b. If the h.c.f. (a,b) is an element of the form (1), then the set of the elements (1) consists exactly of those elements which are divisible by (a,b). This case is of a special interest.

Theorem 1: If the elements of D which ¹ 0 are factorizable and if there exists for every pair a, b of the elements of D an h.c.f. and can be expressed by (1), then D is uniquely factorizable.

Proof: Let ab be divisible by a prime element p, say ab = kp and a not divisible by p, then the highest common factors of a and p are unities ; hence a unity, say e^-l,can be expressed by ca + dp = e^-l, whence

(c e) (a b) + (d e b)p = b = (c e k + d e b)p.

Hence b is divisible by p and the theorem follows from the criterion of 2.4.3.

Let

be elements of the integral domain D satisfying the conditions

Then every common factor of a_k-1 and a_k is also a common factor of a_k and a_k+1 and conversely, and since this property holds for every k, each pair of consecutive elements has the same common factors. If especially a_n+1 = 0, then a_n is the h.c.f. of a_n and a_n-1, whence every pair of consecutive elements of the sequence (2) has an h.c.f. and this factor is equal to a_n. Hence

a_{n =} (a₁,a₂). (4)

The construction of a sequence (2) ending with a_n+1 = 0 is called the Algorithm of the h.c.f. This algorithm allows you to express successively a₃, a₄, ··· , a_n = (a₁, a₂) as linear homogeneous functions of a₁ and a₂. If therefore the elements ¹ 0 of D are factorizable and the algorithm can be performed for every pair of elements, then D is uniquely factorizable. Thus it is very important to have a condition which is sufficient for the working of the algorithm. Let there be determined in an integral domain D a norm-function N which satisfies the conditions explained in 2.4.2. Moreover, let there exist, for every pair of elements a_k-1 ¹ 0 and a_k ¹ 0 of D, elements a_k+1 ¹ 0 and a_k¹0 of D such that

where either a_k+1 = 0 or N(a_k+1) < N(a_k), when D is said to be an Euclidean domain.

Theorem 2: There exists in D for every m-tuplet of elements of a Euclidean domain D an h.c.f. which can be determined by repeated application of the algorithm; the h.c.f. can be represented as a linear homogeneous function of the n elements with coefficients out of D. The factorization in D is unique.

Proof: Since a norm-function exists in D, the elements are factorizable. It follows from (5) that given any two elements a₁ and a₂, one can find a sequence a₁, a₂, ··· in D such that N(a₂) > N(a₁) > ···. As the norms are positive integers, their sequence cannot have more than N(a₂) elements. If N(a_n) is the last norm in the sequence, it follows from (5) that a_n+1 = 0. Hence a_n = (a₁, a₂) can be found by the algorithm and therefore a_n = ba₁ + ca₂, where b and c are elements of D. The theorem holds therefore for m = 2 and the factorization in D is unique. It follows from 2.4.3 Theorem 1 that the h.c.f. of every m-tuplet exists. Let

and this h.c.f. can be found by k - 1 applications of the algorithm, then

can be found by k applications of the algorithm, whence follows the theorem.

2.4.5 The domain of the integral numbers: Consider the domain J of the integral numbers and put

N(a) = |a|.

This function has obviously the properties postulated for a norm function in 2.4.2 (1) and satisfies also the condition 2.4.4 (5) above, whence factorization in J is unique and the h.c.f. can be found by the algorithm. The multiplicative properties of integral numbers are therefore determined by their representation as products of powers of prime numbers. Thus it is important to know that there exists an infinite number of prime numbers.

Proof (Euclid): Suppose there exists only a finite number of prime numbers, say the numbers p_j ( j = 1, ··· , n); then (p₁, p₂, ··· , p_n) + 1 is neither divisible by any prime number nor is it a unity, whence the supposition is wrong and the proposition above is correct.

2.4.8 Homomorphism modulo a prime element: Let D be an integral domain, where factorization is unique and p be any particular prime element in D. The elements which are divisible by p form a sub-ring D_p of D. As has been shown in 2.2.3, the classes of residues of D_p in D form a ring D^p which is homomorphic to D. By this homomorphism, an element a of D is mapped onto an element a of D^p. Hence (a) = (a + kp) for every element k of D. The zero-element (0) of D^p consists of the elements divisible by p, that is, of the elements of D_p. Since D is commutative and D^p is homomorphic to D, the ring D_p is commutative. It will be shown now that D^p is an integral domain. Suppose (a) (b) = (0), then (ab) = (0), whence ab is divisible by p. Since the factorization in D is supposed to be unique and p is a prime element, at least one of the factors a, b must be divisible by p, i.e., one of the elements (a), (b) of D must be the zero element. Moreover, (1) is the unit element of D^p, whence the commutative ring D^p is an integral domain.

2.4.7 Factorization in F[x]: Consider now the domain F[x] of the polynomials in x over a field F (cf. 2.3.4); with the exception of the element 0, there is defined for every element f(x) of F(x) a positive integral norm by

The elements ¹ 0 of F are the unities, Hence N(a) = I holds for unities only. Applying 2.3.4 Theorem 3, we find for non-zero-elements a, b of F(x)

Hence N(a b) ³ N(a), where equality applies if and only if b is a unity.

Let

be two polynomials of F[x]. The condition n ³ m does not involve any loss of generality, since, for example, a may be equal to zero; the condition b_m ¹ 0 merely stops f₂(x) from being the zero element. If

then

where the degree of f₃(x) is less than the degree of f₂(x). Hence

whence follows

Theorem 1: Let f₁(x) and f₂(x) ¹ 0 be polynomials of F [x] (where F denotes a field), then there exist in F [x] polynomials b₂(x) and f₃(x) which satisfy (3) and (4) and these polynomials can be calculated in a finite number of steps.

The method of calculation of b₂(x) and f₃(x) is called the algorithm of division and f₃(x) is the remainder. By Theorem 1, the norm function satisfies the conditions of 2.4.4, whence follows

Theorem 2: F[x] is a Euclidean domain; the h.c.f. of any m elements f ₁, ··· f_m can be represented as a linear homogeneous function

g₁(x)f₁(x) + ··· + g_m(x)f_m(x)

and the factorization is unique.

Note that f₃(x) is uniquely determined by (3) and (4), since if

f₁(x) + c(x)f₂(x) = y(x),

f₃(x) - y(x) is divisible by f₂(x), whence y(x) cannot satisfy the conditions imposed on f₃(x) in (4), unless y(x) = f₃(x). A similar uniqueness does not hold in the domain J of the integral numbers. Indeed

The prime-elements of F[x] are said to be irreducible polynomials. Since polynomials of degree zero are unities, an irreducible polynomial of degree ³ 1 cannot be represented as a product of two polynomials of degree ³ 1. Hence every linear polynomial in x is irreducible over F. A polynomial of degree ³ 1 which is not irreducible is said to be reducible. If F is a sub-field of F₁, every polynomial f(x) of F[x] belongs also to F₁[x]; f(x) may be irreducible in F[x] and reducible in F₁[x]. For example, the polynomial f (x) = x² - 2 is a polynomial of F[x], where F is the field of the rational numbers ; in F[x], the polynomial f(x) is irreducible. Let F₁ be the field of the real numbers, then f(x)=(x - Ö 2)(x + Ö 2) is reducible in F₁[x].

Theorem 3: Let f₁(x) and f₂(x) be two polynomials of F[x] and let there be no common irreducible factor of f₁(x) and f₂(x), then there exist polynomials j₁(x) and j₂(x) of F[x] such that

j₁(x)f₁(x) + j₂(x)f₂(x) = 1. (5)

Proof: Every highest common factor of f₁(x) and f₂(x) is a unity of F(x), i.e., any element a ¹ 0 of F. By Theorem 1, there exist polynomials y₁(x) and y₂(x) satisfying y₁(x)f₁(x) + y₂(x)f₂(x) = a. Setting y_i(x) = aj_i(x) (for i = 1, 2), one finds (5).

In particular, if f₂(x) is irreducible and f₁(x) is not divisible by it, then j₁(x)f₁(x)º1 (mod f₂(x)), i.e.,

j_i(x) º {f₁(x)}^-1 (mod f₂(x)) (6)

In 2.4.6, it has been shown that in an integral domain with unique factorization the classes of residues of a prime element form an integral domain. As F[x] is an integral domain with unique factorization, the classes of residues of f(x) form an integral domain, and as (6) holds, these classes form a field, whence follows

Theorem 4: Let f(x) be irreducible in F(x), then the classes of residues of f(x) in F[x] form a field.

If f(x) is reducible, say f(x) = f(x)y(x), then the classes of residues do not form an integral domain, since f(x) is not a prime element. Of course, between the classes holds the. equation f(x)y(x) = f(x) = 0, although (f(x)) ¹ (0) and (y(x)) ¹ (0).

The elements of the field considered in the last theorem are classes of residues of f(x). Let n be the degree of f(x) and f₁(x) be any polynomial of F[x], then, by the algorithm of division,

f₁(x) - b(x)f(x) = f₃(x),

where f₃(x) is the remainder of the division and therefore of a degree < n. Since f₁(x) - f₃(x) is divisible by f(x), f₃(x) belongs to the same class of residues as f₁(x); thus every class contains a polynomial of degree < n. Let there be two such polynomials, say f₃(x) and f₄(x) in the same class, then f₃(x) - f₄(x) is of degree < n and divisible by f(x), whence it is zero. Thus, in every class, there exists one and only one polynomial of degree < n which characterizes the class. In particular, consider the classes which contain polynomials a₀ of degree <1. These classes form a sub-field which is in a (1, 1) and in isomorphic correspondence with the elements a₀ of F. This sub-field is therefore isomorphic to F, whence follows

Theorem 5: Each of the classes of residues, considered in Theorem 4, contains exactly one polynomial of a degree which is less than the degree of f(x) and characterizes the class. The classes characterized by polynomials of degree < l (i.e., elements of F) form a sub-field which is isomorphic to the field F, every class being represented by its characterizing element.

2.4.8 Factorization in D[x]: Let D be an integral domain with unique factorization. Investigate to start with the divisibility of polynomials f(x) of D[x] by elements of D. In the special case where D is a field, every f(x) is divisible by every element of D which differs from zero as these elements are unities. This special case has been investigated in 2.4.7.

If f(x) is divisible by an element c

whence every coefficients of f(x) is divisible by c. If the h.c.f. of the coefficients of f(x) is equal to 1, then f(x) is divisible by unities only, and conversely. In this case, f(x) is said to be a primitive polynomial of D[x].

Let p be any prime element of D; as in 2.4.6, the sub-ring of the elements which are divisible by p will be denoted by D_p.

Then D_p[x] consists of the polynomials the coefficients of which are divisible by p, whereas {D[x]}_p consists of the polynomials of D[x] which are divisible by p. Equation (1) now yields

D_p[x] = {D[x]}_p. (2)

As the factorization in D is unique, the classes of residues of D_p in D form an integral domain D ^p of which D_p is the zero element (cf. 2.4.6); by 2.3.4 Theorem 2, D^p[x] is also an integral domain of which the class D_p[x] is the zero element. The classes of residues of D[x] form a ring {D[x]}^p which is isomorphic to D^p[x] and is therefore an integral domain. Let f(x) = f₁(x) f₂(x) be divisible by p, then f(x) belongs to the zero element {D[x]}_p of {D[x]}^p and therefore at least one of the two factors is divisible by p, whence follows the

Lemma: If the factorization in D is unique and p is a prime-element of D, and moreover f₁(x) and f₂(x) belong to D[x], and f₁(x)f₂(x) is divisible by p, then at least one of the factors f₁(x) and f₂(x) is divisible by p.

Corollary 1: If f₁(x) and f₂(x) are primitive polynomials, then f₁(x) f₂(x) is primitive.

Corollary 2: If af(x) is divisible by a primitive polynomial f(x), then f(x) is divisible by f(x).

Proof: Since a belongs to D, it is factorizable; a = p₁, p₂, ··· , p_n. Let

af(x) = f(x)f₁(x).

Since f(x) is primitive, it is not divisible by p₁, whence, by Theorem 1, f₁(x)=p₁f₂(x) and therefore

p₂ ··· p_nf(x) = f(x)f₂(x).

By n-fold repetition of this procedure, one finds

f(x) = f(x)f_n+1(x).

Corollary 3: If f(x) is factorizable in D[x], then f(x) = a₁ ··· a_mf₁(x) ··· f_n(x), where f₁(x) ··· f_n(x) are primitive, and a₁ ··· a_m = a is the factorization in D of the h. c. f. of the coefficients of f(x).

Proof: A prime element of D[x] is either an element of D or it is a primitive polynomial, since a polynomial is not a prime element, if the coefficients have a common non-unity factor. Let f₁(x), ··· , f_n(x) be the primitive polynomials of degree > 0 among the prime factors of f(x), then their product is a primitive polynomial, say f(x). The product of the prime factors of f(x), belonging to D, is an element a of D. Thus, f(x) = af(x), whence a is the h.c.f. of the coefficients of f(x). The factors a_n of a are prime in D[x], whence they are also prime elements of D and a = a₁ ··· a_m is a factorization of a in D.

Theorem: If the factorization in D is unique, so is the factorization in D[x].

Proof: Since D is an integral domain, there exists a quotient field F, of which D is a sub-ring; every element of F is the quotient of two elements of D. Let f(x) be a primitive polynomial of D[x], then is also a polynomial of F[x] and it is uniquely factorizable in F[x]:

f(x) = f₁(x) ··· f_n(x).

The factors f_i(x) are determined up to a unity of F[x], i.e., up to an element of F. Since the coefficients of f_i(x) are quotients of elements of D, there exists an element b_i such that b_if_i(x) is a polynomial in D[x], whence

b_if_i(x) = c_if_i(x),

where f_i(x) is primitive. f_i(x) and f_i(x) are associated in F[x], whence f_i(x) is a prime element of F[x], moreover f_i(x) is a prime element in D[x], otherwise it must be a product of primitive polynomials in D[x] contrary to the fact that it is a prime element of F[x]. Setting b₁ ··· b_n = b, c₁ ··· c_n = c, one finds

bf(x) = cf₁(x) ··· f_n(x).

It follows from Corollaries 1 and 2 that the primitive polynomials f(x) and f₁(x) ··· f₂(x) are divisible one by the other and are therefore associated, whence

f(x) = ef₁(x) ··· f_n(x),

where e is a unity and f₁(x) ··· f_n(x) are prime elements of F[x] as well as of D[x]. In the special case when f(x) is a prime element of D[x], the number n is equal to 1. Every prime.element of D[x] which does not belong to D is therefore also a prime element of F[x]. Since the factorization of f(x) in F[x] is unique, the primitive polynomial f(x) is factorizable in D[x] into prime elements f_i(x) of D[x] which are determined up to unities of F[x], i.e., up to elements of F. But since each f_i(x) is primitive, these elements must be unities of D. Hence f(x) is uniquely factorizable into the prime factors of a and those of f_i(x) (i=1,···, n), these factorizations being unique. On the other hand, it follows from Corollary 3 that every factorization of af(x) consists of a factorization of a and a factorization of f(x). Hence follows the theorem.

This theorem may be viewed as a generalization of 2.4.7 Theorem 1, but it does not generalize its full statement. Of course, D[x] is not necessarily a Euclidean domain, even if D is. For example, consider the domain J of the integral numbers which has been proved to be Euclidean. a(x) = x—2 and b(x) = x + 2 are primitive polynomials of J[x] and of degree 1,whence they are prime elements. Since ± 1 are the only unities, they are not associated, whence (a(x), b(x)) = 1. If this h.c.f. were linearly dependent on a(x) and b(x), say

then this equation must hold when x is replaced by any element of J; for x = 0, one gets — 2 u(0) + 2 v(0) which is obviously even and therefore ¹ 1, whence J[x] is not Euclidean.

Exercise: Let a(x) and b(x) be two polynomials of E[x], where E is a Euclidean domain. Show that f(x) = a(x) u(x) + b(x)v(x) if and only if f(x) is divisible by a particular polynomial.

2.4.9 Comparison between R and R[x]: If the factorization in D is unique, then the same holds for

Hence the polynomials in n variables form a uniquely factorizable domain, if the coefficients run over a uniquely factorizable ring, e.g., a field of the domain J of the integral numbers. On the other hand, starting from a domain of this kind, one gets again integral domains by a homomorphism which maps a particular prime element and its multiples onto zero. In 2.3 and 2.4, two methods have been developed to generate new rings, integral domains and fields from given ones; these two procedures are of fundamental importance for General Algebra. One method involves the construction of a ring of polynomials over a given ring, the other is a homomorphism by which a suitable sub-ring is mapped onto zero. The following list of results may be useful:

Moreover: If in D the factorization is unique and D_p is the sub-ring of the elements which are divisible by a particular prime element p, then D is mapped onto an integral domain D^p by the homomorphism mapping D_v onto zero [cf. 2.4.6]. It is not necessary for D^p to have a unique factorization.

In particular, if D = F[x], where F is a field, then D ^p is a field, (cf. 2.4.7 Theorem 4).