1000/1000

Hot
Most Recent

Submitted Successfully!

Thank you for your contribution! You can also upload a video entry or images related to this topic.

Do you have a full video?

Are you sure to Delete?

Cite

If you have any further questions, please contact Encyclopedia Editorial Office.

Xu, H. Gauss's Lemma (Polynomial). Encyclopedia. Available online: https://encyclopedia.pub/entry/36796 (accessed on 11 December 2023).

Xu H. Gauss's Lemma (Polynomial). Encyclopedia. Available at: https://encyclopedia.pub/entry/36796. Accessed December 11, 2023.

Xu, Handwiki. "Gauss's Lemma (Polynomial)" *Encyclopedia*, https://encyclopedia.pub/entry/36796 (accessed December 11, 2023).

Xu, H.(2022, November 28). Gauss's Lemma (Polynomial). In *Encyclopedia*. https://encyclopedia.pub/entry/36796

Xu, Handwiki. "Gauss's Lemma (Polynomial)." *Encyclopedia*. Web. 28 November, 2022.

Copy Citation

In algebra, Gauss's lemma, named after Carl Friedrich Gauss, is a statement about polynomials over the integers, or, more generally, over a unique factorization domain (that is, a ring that has a unique factorization property similar to the fundamental theorem of arithmetic). Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials. Gauss's lemma asserts that the product of two primitive polynomials is primitive (a polynomial with integer coefficients is primitive if it has 1 as a greatest common divisor of its coefficients). A corollary of Gauss's lemma, sometimes also called Gauss's lemma, is that a primitive polynomial is irreducible over the integers if and only if it is irreducible over the rational numbers. More generally, a primitive polynomial has the same complete factorization over the integers and over the rational numbers. In the case of coefficients in a unique factorization domain R, "rational numbers" must be replaced by "field of fractions of R". This implies that, if R is either a field, the ring of integers, or a unique factorization domain, then every polynomial ring (in one or several indeterminates) over R is a unique factorization domain. Another consequence is that factorization and greatest common divisor computation of polynomials with integers or rational coefficients may be reduced to similar computations on integers and primitive polynomials. This is systematically used (explicitly or implicitly) in all implemented algorithms (see Polynomial greatest common divisor and Factorization of polynomials). Gauss's lemma, and all its consequences that do not involve the existence of a complete factorization remain true over any GCD domain (an integral domain over which greatest common divisors exist). In particular, a polynomial ring over a GCD domain is also a GCD domain. If one calls primitive a polynomial such that the coefficients generate the unit ideal, Gauss's lemma is true over every commutative ring. However, some care must be taken, when using this definition of primitive, as, over a unique factorization domain that is not a principal ideal domain, there are polynomials that are primitive in the above sense and not primitive in this new sense.

primitive polynomial
greatest common divisor
unique factorization

If [math]\displaystyle{ F(X) = a_0 + a_1 X + \dots + a_n X^n }[/math] is a polynomial with integer coefficients, then [math]\displaystyle{ F }[/math] is called *primitive* if the greatest common divisor of all the coefficients [math]\displaystyle{ a_0, a_1, \dots, a_n }[/math] is 1; in other words, no prime number divides all the coefficients.

**Gauss's lemma (primitivity)** — If *P* and *Q* are primitive polynomials over the integers, then product *PQ* is also primitive.

**Proof:** Clearly the product *f*(*x*).*g*(*x*) of two primitive polynomials has integer coefficients. Therefore, if it is not primitive, there must be a prime *p* which is a common divisor of all its coefficients. But *p* can not divide all the coefficients of either *f*(*x*) or *g*(*x*) (otherwise they would not be primitive). Let *a _{r}x^{r}* be the first term of

- [math]\displaystyle{ a_r b_s + a_{r+1} b_{s-1} + a_{r+2} b_{s-2} + \cdots + a_{r-1} b_{s+1} + a_{r-2} b_{s+2} + \cdots\, }[/math]

The first term is not divisible by *p* (because *p* is prime), yet all the remaining ones are, so the entire sum cannot be divisible by *p*. By assumption all coefficients in the product are divisible by *p*, leading to a contradiction. Therefore, the coefficients of the product can have no common divisor and are thus primitive. [math]\displaystyle{ \square }[/math]

**Gauss's lemma (irreducibility)** — A non-constant polynomial in **Z**[*X*] is irreducible in **Z**[*X*] if and only if it is both irreducible in **Q**[*X*] and primitive in **Z**[*X*].

The proof is given below for the more general case. Note that an irreducible element of **Z** (a prime number) is still irreducible when viewed as constant polynomial in **Z**[*X*]; this explains the need for "non-constant" in the statement.

Gauss's lemma holds more generally over arbitrary unique factorization domains. There the *content* *c*(*P*) of a polynomial *P* can be defined as the greatest common divisor of the coefficients of *P* (like the gcd, the content is actually a set of associate elements). A polynomial *P* with coefficients in a UFD is then said to be **primitive** if the only elements of *R* that divide all coefficients of *P* at once are the invertible elements of *R*; i.e., the gcd of the coefficients is one.

**Primitivity statement:** If *R* is a UFD, then the set of primitive polynomials in *R*[*X*] is closed under multiplication. More generally, the content of a product [math]\displaystyle{ fg }[/math] of polynomials is the product [math]\displaystyle{ c(f)c(g) }[/math] of their contents.

**Irreducibility statement:** Let *R* be a unique factorization domain and *F* its field of fractions. A non-constant polynomial [math]\displaystyle{ f }[/math] in [math]\displaystyle{ R[x] }[/math] is irreducible in [math]\displaystyle{ R[x] }[/math] if and only if it is both irreducible in [math]\displaystyle{ F[x] }[/math] and primitive in [math]\displaystyle{ R[x] }[/math].

(For the proofs, see #General version below.)

Let [math]\displaystyle{ R }[/math] be a unique factorization domain with field of fractions [math]\displaystyle{ F }[/math]. If [math]\displaystyle{ f \in F[x] }[/math] is a polynomial over [math]\displaystyle{ F }[/math], then, for some [math]\displaystyle{ d \in R }[/math], [math]\displaystyle{ df }[/math] has coefficients in [math]\displaystyle{ R }[/math] and so, factoring-out the gcd [math]\displaystyle{ q }[/math] of the coefficients, we can write: [math]\displaystyle{ df = qf' }[/math] for some primitive polynomial [math]\displaystyle{ f' \in R[x] }[/math]. As one can check, this polynomial [math]\displaystyle{ f' }[/math] is unique up to the multiplication by a unit element and is called the **primitive part** (or **primitive representative**) of [math]\displaystyle{ f }[/math] and is denoted by [math]\displaystyle{ \operatorname{pp}(f) }[/math]. The procedure is compatible with product: [math]\displaystyle{ \operatorname{pp}(fg) = \operatorname{pp}(f)\operatorname{pp}(g) }[/math].

The construct can be used to show the statement:

- A polynomial ring over a UFD is a UFD.

Indeed, by induction, it is enough to show [math]\displaystyle{ R[x] }[/math] is a UFD when [math]\displaystyle{ R }[/math] is a UFD. Let [math]\displaystyle{ f \in R[x] }[/math] be a nonzero polynomial. Now, [math]\displaystyle{ F[x] }[/math] is a unique factorization domain (since it is a principal ideal domain) and so, as a polynomial in [math]\displaystyle{ F[x] }[/math], [math]\displaystyle{ f }[/math] can be factorized as:

- [math]\displaystyle{ f = g_1 g_2 \dots g_r }[/math]

where [math]\displaystyle{ g_i }[/math] are irreducible polynomials of [math]\displaystyle{ F[x] }[/math]. Now, we write [math]\displaystyle{ f = c f' }[/math] for the gcd [math]\displaystyle{ c }[/math] of the coefficients of [math]\displaystyle{ f }[/math] (and [math]\displaystyle{ f' }[/math] is the primitive part) and then:

- [math]\displaystyle{ f = c f' = c \operatorname{pp}(g_1) \operatorname{pp}(g_2) \cdots \operatorname{pp}(g_r). }[/math]

Now, [math]\displaystyle{ c }[/math] is a product of prime elements of [math]\displaystyle{ R }[/math] (since [math]\displaystyle{ R }[/math] is a UFD) and a prime element of [math]\displaystyle{ R }[/math] is a prime element of [math]\displaystyle{ R[x] }[/math], as [math]\displaystyle{ R[x]/(p) \cong R/(p)[x] }[/math] is an integral domain. Hence, [math]\displaystyle{ c }[/math] admits a prime factorization (or a unique factorization into irreducibles). Next, observe that [math]\displaystyle{ f' = \operatorname{pp}(g_1) \cdots \operatorname{pp}(g_r) }[/math] is a unique factorization into irreducible elements of [math]\displaystyle{ R[x] }[/math], as (1) each [math]\displaystyle{ \operatorname{pp}(g_i) }[/math] is irreducible by the irreducibility statement and (2) it is unique since the factorization of [math]\displaystyle{ f' }[/math] can also be viewed as a factorization in [math]\displaystyle{ F[x] }[/math] and factorization there is unique. Since [math]\displaystyle{ c, f' }[/math] are uniquely determined by [math]\displaystyle{ f }[/math], up to unit elements, the above factorization of [math]\displaystyle{ f }[/math] is a unique factorization into irreducible elements. [math]\displaystyle{ \square }[/math]

The condition that "*R* is a unique factorization domain" is not superfluous because it implies that every irreducible element of this ring is also a prime element, which in turn implies that every nonzero element of *R* has at most one factorization into a product of irreducible elements and a unit up to order and associate relationship. In a ring where factorization is not unique, say *pa* = *qb* with *p* and *q* irreducible elements that do not divide any of the factors on the other side, the product (*p* + *qX*)(*a* + *qX*) = *pa* + (*p*+*a*)*qX* + *q ^{2}X^{2}* =

Let [math]\displaystyle{ R }[/math] be a commutative ring. If [math]\displaystyle{ f }[/math] is a polynomial in [math]\displaystyle{ R[x_1, \dots, x_n] }[/math], then we write [math]\displaystyle{ \operatorname{cont}(f) }[/math] for the ideal of [math]\displaystyle{ R }[/math] generated by all the coefficients of [math]\displaystyle{ f }[/math]; it is called the content of [math]\displaystyle{ f }[/math]. Note that [math]\displaystyle{ \operatorname{cont}(af) = a\operatorname{cont}(f) }[/math] for each [math]\displaystyle{ a \in R }[/math]. The next proposition states a more substantial property.

**Proposition ^{[1]}** — For each pair of polynomials [math]\displaystyle{ f, g }[/math] in [math]\displaystyle{ R[x_1, \dots, x_n] }[/math],

- [math]\displaystyle{ \operatorname{cont}(fg) \subset \operatorname{cont}(f)\operatorname{cont}(g) \subset \sqrt{\operatorname{cont}(fg)} }[/math]

where [math]\displaystyle{ \sqrt{\cdot} }[/math] denotes the radical of an ideal. Moreover, if [math]\displaystyle{ R }[/math] is a GCD domain (e.g., a unique factorization domain), then

- [math]\displaystyle{ \operatorname{gcd}(\operatorname{cont}(fg)) = \operatorname{gcd}(\operatorname{cont}(f)) \operatorname{gcd}(\operatorname{cont}(g)) }[/math]

where [math]\displaystyle{ \operatorname{gcd}(I) }[/math] denotes the unique minimal principal ideal containing a finitely generated ideal [math]\displaystyle{ I }[/math].^{[2]}

A polynomial [math]\displaystyle{ f }[/math] is said to be *primitive* if [math]\displaystyle{ \operatorname{cont}(f) = (1) }[/math] is the unit ideal.^{[3]} When [math]\displaystyle{ R = \mathbb{Z} }[/math] (or more generally a Bézout domain), this agrees with the usual definition of a primitive polynomial. (But if [math]\displaystyle{ R }[/math] is only a UFD, this definition is inconsistent with the definition of primitivity in #Statements for unique factorization domains.)

**Corollary ^{[4]}** — Two polynomials [math]\displaystyle{ f, g }[/math] are primitive if and only if the product [math]\displaystyle{ fg }[/math] is primitive.

*Proof:* This is easy using the fact^{[5]} that [math]\displaystyle{ \sqrt{I} = (1) }[/math] implies [math]\displaystyle{ I = (1). }[/math] [math]\displaystyle{ \square }[/math]

**Corollary ^{[6]}** — Suppose [math]\displaystyle{ R }[/math] is a GCD domain (e.g., a unique factorization domain) with the field of fractions [math]\displaystyle{ F }[/math]. Then a non-constant polynomial [math]\displaystyle{ f }[/math] in [math]\displaystyle{ R[x] }[/math] is irreducible if and only if it is irreducible in [math]\displaystyle{ F[x] }[/math] and the gcd of the coefficients of [math]\displaystyle{ f }[/math] is 1.

*Proof:* ([math]\displaystyle{ \Rightarrow }[/math]) First note that the gcd of the coefficients of [math]\displaystyle{ f }[/math] is 1 since, otherwise, we can factor out some element [math]\displaystyle{ c \in R }[/math] from the coefficients of [math]\displaystyle{ f }[/math] to write [math]\displaystyle{ f = cf' }[/math], contradicting the irreducibility of [math]\displaystyle{ f }[/math]. Next, suppose [math]\displaystyle{ f = gh }[/math] for some non-constant polynomials [math]\displaystyle{ g, h }[/math] in [math]\displaystyle{ F[x_1, \dots, x_n] }[/math]. Then, for some [math]\displaystyle{ d \in R }[/math], the polynomial [math]\displaystyle{ dg }[/math] has coefficients in [math]\displaystyle{ R }[/math] and so, by factoring out the gcd [math]\displaystyle{ q }[/math] of the coefficients, we write [math]\displaystyle{ dg = qg' }[/math]. Do the same for [math]\displaystyle{ h }[/math] and we can write [math]\displaystyle{ f = c g'h' }[/math] for some [math]\displaystyle{ c \in F }[/math]. Now, let [math]\displaystyle{ c = a/b }[/math] for some [math]\displaystyle{ a, b \in R }[/math]. Then [math]\displaystyle{ bf = a g'h' }[/math]. From this, using the proposition, we get:

- [math]\displaystyle{ (b) \supset \operatorname{gcd}(\operatorname{cont}(bf)) = (a) }[/math].

That is, [math]\displaystyle{ b }[/math] divides [math]\displaystyle{ a }[/math]. Thus, [math]\displaystyle{ c \in R }[/math] and then the factorization [math]\displaystyle{ f = c g'h' }[/math] constitutes a contradiction to the irreducibility of [math]\displaystyle{ f }[/math].

([math]\displaystyle{ \Leftarrow }[/math]) If [math]\displaystyle{ f }[/math] is irreducible over [math]\displaystyle{ F }[/math], then either it is irreducible over [math]\displaystyle{ R }[/math] or it contains a constant polynomial as a factor, the second possibility is ruled out by the assumption. [math]\displaystyle{ \square }[/math]

*Proof of the proposition:* Clearly, [math]\displaystyle{ \operatorname{cont}(fg) \subset \operatorname{cont}(f) \operatorname{cont}(g) }[/math]. If [math]\displaystyle{ \mathfrak{p} }[/math] is a prime ideal containing [math]\displaystyle{ \operatorname{cont}(fg) }[/math], then [math]\displaystyle{ fg \equiv 0 }[/math] modulo [math]\displaystyle{ \mathfrak{p} }[/math]. Since [math]\displaystyle{ R/\mathfrak{p}[x_1, \dots, x_n] }[/math] is a polynomial ring over an integral domain and thus is an integral domain, this implies either [math]\displaystyle{ f \equiv 0 }[/math] or [math]\displaystyle{ g \equiv 0 }[/math] modulo [math]\displaystyle{ \mathfrak{p} }[/math]. Hence, either [math]\displaystyle{ \operatorname{cont}(f) }[/math] or [math]\displaystyle{ \operatorname{cont}(g) }[/math] is contained in [math]\displaystyle{ \mathfrak{p} }[/math]. Since [math]\displaystyle{ \sqrt{\operatorname{cont}(fg)} }[/math] is the intersection of all prime ideals that contain [math]\displaystyle{ \operatorname{cont}(fg) }[/math] and the choice of [math]\displaystyle{ \mathfrak p }[/math] was arbitrary, [math]\displaystyle{ \operatorname{cont}(f) \operatorname{cont}(g) \subset \sqrt{\operatorname{cont}(fg)} }[/math].

We now prove the "moreover" part. Factoring out the gcd’s from the coefficients, we can write [math]\displaystyle{ f = a f' }[/math] and [math]\displaystyle{ g = b g' }[/math] where the gcds of the coefficients of [math]\displaystyle{ f', g' }[/math] are both 1. Clearly, it is enough to prove the assertion when [math]\displaystyle{ f, g }[/math] are replaced by [math]\displaystyle{ f', g' }[/math]; thus, we assume the gcd's of the coefficients of [math]\displaystyle{ f, g }[/math] are both 1. The rest of the proof is easy and transparent if [math]\displaystyle{ R }[/math] is a unique factorization domain; thus we give the proof in that case here (and see ^{[7]} for the proof for the GCD case). If [math]\displaystyle{ \gcd(\operatorname{cont}(fg)) = (1) }[/math], then there is nothing to prove. So, assume otherwise; then there is a non-unit element dividing the coefficients of [math]\displaystyle{ fg }[/math]. Factorizing that element into a product of prime elements, we can take that element to be a prime element [math]\displaystyle{ \pi }[/math]. Now, we have:

- [math]\displaystyle{ (\pi) = \sqrt{(\pi)} \supset \sqrt{\operatorname{cont}(fg)} \supset \operatorname{cont}(f) \operatorname{cont}(g) }[/math].

Thus, either [math]\displaystyle{ (\pi) }[/math] contains [math]\displaystyle{ \operatorname{cont}(f) }[/math] or [math]\displaystyle{ \operatorname{cont}(g) }[/math]; contradicting the gcd's of the coefficients of [math]\displaystyle{ f, g }[/math] are both 1. [math]\displaystyle{ \square }[/math]

**Remark**: Over a GCD domain (e.g., a unique factorization domain), the gcd of all the coefficients of a polynomial [math]\displaystyle{ f }[/math], unique up to unit elements, is also called the content of [math]\displaystyle{ f }[/math].

It follows from Gauss's lemma that for each unique factorization domain [math]\displaystyle{ R }[/math], the polynomial ring [math]\displaystyle{ R[X_1, X_2,. .., X_n] }[/math] is also a unique factorization domain (see #Statements for unique factorization domains). Gauss's lemma can also be used to show Eisenstein's irreducibility criterion. Finally, it can be used to show that cyclotomic polynomials (unitary units with integer coefficients) are irreducible.

Gauss's lemma implies the following statement:

- If [math]\displaystyle{ f(x) }[/math] is a monic polynomial in one variable with coefficients in a unique factorization domain [math]\displaystyle{ R }[/math] (or more generally a GCD domain), then a root of [math]\displaystyle{ f }[/math] that is in the field of fractions [math]\displaystyle{ F }[/math] of [math]\displaystyle{ R }[/math] is in [math]\displaystyle{ R }[/math].
^{[8]}

If [math]\displaystyle{ R = \mathbb{Z} }[/math], then it says a rational root of a monic polynomial over integers is an integer (cf. the rational root theorem). To see the statement, let [math]\displaystyle{ a/b }[/math] be a root of [math]\displaystyle{ f }[/math] in [math]\displaystyle{ F }[/math] and assume [math]\displaystyle{ a, b }[/math] are relatively prime. In [math]\displaystyle{ F[x] }[/math], we can write [math]\displaystyle{ f = (x - a/b)g }[/math] with [math]\displaystyle{ cg \in R[x] }[/math] for some [math]\displaystyle{ c \in R }[/math]. Then

- [math]\displaystyle{ cb f = (bx - a)cg }[/math],

is a factorization in [math]\displaystyle{ R[x] }[/math]. But [math]\displaystyle{ bx - a }[/math] is primitive (in the UFD sense) and thus [math]\displaystyle{ cb }[/math] divides the coefficients of [math]\displaystyle{ cg }[/math] by Gauss's lemma and so

- [math]\displaystyle{ f = (bx - a)h }[/math],

with [math]\displaystyle{ h }[/math] in [math]\displaystyle{ R[x] }[/math]. Since [math]\displaystyle{ f }[/math] is monic, this is possible only when [math]\displaystyle{ b }[/math] is a unit.

A similar argument shows:

- Let [math]\displaystyle{ R }[/math] be a GCD domain with the field of fractions [math]\displaystyle{ F }[/math] and [math]\displaystyle{ f \in R[x] }[/math]. If [math]\displaystyle{ f = gh }[/math] for some polynomial [math]\displaystyle{ g \in R[x] }[/math] that is primitive in the UFD sense and [math]\displaystyle{ h \in F[x] }[/math], then [math]\displaystyle{ h \in R[x] }[/math].

The irreducibility statement also implies that the minimal polynomial over the rational numbers of an algebraic integer has integer coefficients.

- Eisenbud, Exercise 3.4. (a)
- A generator of the principal ideal is a gcd of some generators of I (and it exists because [math]\displaystyle{ R }[/math] is a GCD domain).
- Atiyah & MacDonald, Ch. 1., Exercise 2. (iv)
- Atiyah & MacDonald, Ch. 1., Exercise 2. (iv) and Exercise 3.
- Atiyah & MacDonald, Ch. 1., Exercise 1.13.
- Eisenbud, Exercise 3.4.c; The case when R is a UFD.
- Proof for the GCD case: The proof here is adopted from Mines, R.; Richman, F.; Ruitenburg, W. (1988). A Course in Constructive Algebra. Universitext. Springer-Verlag. ISBN 0-387-96640-4. We need the following simple lemma about gcd: If [math]\displaystyle{ \gcd(a, b) = \gcd(a, c) = 1 }[/math], then [math]\displaystyle{ \gcd(a, bc) = 1 }[/math]. (The proof of the lemma is not trivial but is by elementary algebra.) We argue by induction on the sum of the numbers of the terms in [math]\displaystyle{ f, g }[/math]; that is, we assume the proposition has been established for any pair of polynomials with one less total number of the terms. Let [math]\displaystyle{ (c) = \gcd(\operatorname(fg)) }[/math]; i.e., [math]\displaystyle{ c }[/math] is the gcd of the coefficients of [math]\displaystyle{ fg }[/math]. Assume [math]\displaystyle{ (c) \ne (1) }[/math]; otherwise, we are done. Let [math]\displaystyle{ f_0, g_0 }[/math] denote the highest-degree terms of [math]\displaystyle{ f, g }[/math] in terms of lexicographical monomial ordering. Then [math]\displaystyle{ f_0g_0 }[/math] is precisely the leading term of [math]\displaystyle{ fg }[/math] and so [math]\displaystyle{ c }[/math] divides the (unique) coefficient of [math]\displaystyle{ f_0g_0 }[/math] (since it divides all the coefficients of [math]\displaystyle{ fg }[/math]). Now, if [math]\displaystyle{ c }[/math] does not have a common factor with the (unique) coefficient of [math]\displaystyle{ f_0 }[/math] and does not have a common factor with that of [math]\displaystyle{ g_0 }[/math], then, by the above lemma, [math]\displaystyle{ \gcd(c, \operatorname(f_0g_0)) = (1) }[/math]. But [math]\displaystyle{ c }[/math] divides the coefficient of [math]\displaystyle{ f_0g_0 }[/math]; so this is a contradiction. Thus, either [math]\displaystyle{ c }[/math] has a common factor with the coefficient of [math]\displaystyle{ f_0 }[/math] or does with that of [math]\displaystyle{ g_0 }[/math]; say, the former is the case. Let [math]\displaystyle{ (d) = \operatorname(c, \operatorname(f_0)) }[/math]. Since [math]\displaystyle{ d }[/math] divides the coefficients of [math]\displaystyle{ fg - f_0g = (f - f_0)g }[/math], by inductive hypothesis, [math]\displaystyle{ (d) \supset \operatorname(\operatorname((f - f_0)g)) = \operatorname(\operatorname(f - f_0)) \operatorname(\operatorname(g)) = \operatorname(\operatorname(f - f_0)) }[/math]. Since [math]\displaystyle{ (d) }[/math] contains [math]\displaystyle{ \operatorname(f_0) }[/math], it contains [math]\displaystyle{ \operatorname(f) }[/math]; i.e., [math]\displaystyle{ (d) = (1) }[/math], a contradiction. [math]\displaystyle{ \square }[/math]
- In other words, it says that a unique factorization domain is integrally closed.

More

Information

Subjects:
Others

Contributor
MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register
:

View Times:
1587

Entry Collection:
HandWiki

Update Date:
28 Nov 2022