Gauss's lemma (polynomial)

In algebra, in the theory of polynomials (a subfield of ring theory), Gauss's lemma is either of two related statements about polynomials with integer coefficients:

• The first result states that the product of two primitive polynomials is primitive (a polynomial with integer coefficients is called primitive if the greatest common divisor of its coefficients is 1).
• The second result states that if a non-constant polynomial with integer coefficients is irreducible over the integers, then it is also irreducible if it is considered as a polynomial over the rationals.

This second statement is a consequence of the first (see proof below). The first statement and proof of the lemma is in Article 42 of Carl Friedrich Gauss's Disquisitiones Arithmeticae (1801).

Formal statements

The notion of primitive polynomial used here (which differs from the notion with the same name in the context of finite fields) is defined in any polynomial ring R[X] where R is an integral domain: a polynomial P in R[X] is primitive if the only elements of R that divide all coefficients of P at once are the invertible elements of R. In the case where R is the ring Z of the integers, this is equivalent to the condition that no prime number divides all the coefficients of P. The notion of irreducible element is defined in any integral domain: an element is irreducible if it is not invertible and cannot be written as a product of two non-invertible elements. In the case of a polynomial ring R[X], this means that a non-constant irreducible polynomial is one that is not a product of two non-constant polynomials and which is primitive (because being primitive excludes precisely non-invertible constant polynomials as factors). Note that an irreducible element of R is still irreducible when viewed as constant polynomial in R[X]; this explains the need for "non-constant" above, and in the irreducibility statements below.

The two properties of polynomials with integer coefficients can now be formulated formally as follows:

• Primitivity statement: The set of primitive polynomials in Z[X] is closed under multiplication: if P and Q are primitive polynomials then so is their product PQ.

• Irreducibility statement: 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].

These statements can be generalized to any unique factorization domain (UFD), where they become

• Primitivity statement: If R is a UFD, then the set of primitive polynomials in R[X] is closed under multiplication.

• Irreducibility statement: Let R be a UFD and F its field of fractions. A non-constant polynomial in R[X] is irreducible in R[X] if and only if it is both irreducible in F[X] and primitive in R[X].

The condition that R is a UFD is not superfluous. 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

shows the failure of the primitivity statement. For a concrete example one can take

In this example the polynomial 3 + 2X + 2X² (obtained by dividing the right hand side by q = 2) provides an example of the failure of the irreducibility statement (it is irreducible over R, but reducible over its field of fractions Q[√−5]). Another well known example is the polynomial X² − X − 1, whose roots are the golden ratio φ = (1+√5)/2 and its conjugate (1−√5)/2 showing that it is reducible over the field Q[√5], although it is irreducible over the non-UFD Z[√5] which has Q[√5] as field of fractions. In the latter example the ring can be made into an UFD by taking its integral closure Z[φ] in Q[√5] (the ring of Dirichlet integers), over which X² − X − 1 becomes reducible, but in the former example R is already integrally closed.

Proofs of the primitivity statement

An elementary proof of the statement that the product of primitive polynomials over Z is again primitive can be given as follows.

Proof: Suppose the product of two primitive polynomials f(x) and g(x) is not primitive, so there exists a prime number p that is a common divisor of all the coefficients of the product. But since f(x) and g(x) are primitive, p cannot divide either all the coefficients of f(x) or all those of g(x). Let a_rx^r and b_sx^s be the first (i.e., highest degree) terms respectively of f(x) and of g(x) with a coefficient not divisible by p. Now consider the coefficient of x^r+s in the product. Its value is given by

This sum contains a term a_rb_s which is not divisible by p (because p is prime, by Euclid's lemma), yet all the remaining ones are (because either i > r or j > s), so the entire sum is not divisible by p. But 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. This completes the proof.

A cleaner version of this proof can be given using the statement from abstract algebra that a polynomial ring over an integral domain is again an integral domain. We formulate this proof directly for the case of polynomials over a UFD R, which is hardly different from its special case for R = Z.

Proof: Let S,T be primitive polynomials in R[X], and assume that their product ST is not primitive, so that some noninvertible element d of R divides all coefficients of ST. There is some irreducible element p of R that divides d, and it is also a prime element in R (since R is a UFD). Then the principal ideal pR generated by p is a prime ideal, so R/pR is an integral domain, and (R/pR)[X] is therefore an integral domain as well. By hypothesis the projection R[X]→(R/pR)[X] sends ST to 0, and also at least one of S,T individually, which means that p divides all of its coefficients, contradicting primitivity.

The somewhat tedious bookkeeping in the first proof is simplified by the fact that the reduction modulo p kills the uninteresting terms; what is left is a proof that polynomials over an integral domain cannot be zero divisors by consideration of the leading coefficient of their product.

A variation, valid over arbitrary commutative rings

Gauss's lemma is not valid over general integral domains. However there is a variation of Gauss's lemma that is valid even for polynomials over any commutative ring R, which replaces primitivity by the stronger property of co-maximality (which is however equivalent to primitivity in the case of a Bézout domain, and in particular of a principal ideal domain). Call a polynomial P in R[X] co-maximal if the ideal of R generated by the coefficients of the polynomial is the full ring R (when R is a UFD that is not a PID, then co-maximality is much more restrictive than primitivity). The variation of Gauss's lemma says: the product of two co-maximal polynomials is co-maximal.

Proof: Let S,T be co-maximal polynomials in R[X], and assume that their product ST is not co-maximal. Then its coefficients generate a proper ideal I, which by Krull's theorem (which depends on the axiom of choice) is contained in a maximal ideal m of R.Then R/m is a field, and (R/m)[X] is therefore an integral domain. By hypothesis the projection R[X]→(R/m)[X] sends ST to 0, and also at least one of S,T individually, which means that its coefficients all lie in m, which contradicts the fact that they generate the whole ring as an ideal.

A proof valid over any GCD domain

Gauss's lemma holds over arbitrary GCD domains. There the contents c(P) of a polynomial P can be defined as the greatest common divisor of the coefficients of P (like the gcd, the contents is actually a class of associate elements). The primitivity statement can be generalized to the statement that the contents of a product ST of polynomials is the product c(S)c(T) of their contents; in fact this is equivalent to the primitivity statement since c(S)c(T) is certainly a common divisor of the coefficients of the product, so one can divide by c(S) and c(T) to reduce S and T to primitive polynomials. However the proof given above cannot be used when R is a GCD domain, since it uses irreducible factors, which need not exist in such R. Here is a proof that is valid in this context.^[1]

We proceed by induction on the total number of nonzero terms of S and T combined. If one of the polynomials has at most one term, the result is obvious; this covers in particular all cases with fewer than 4 nonzero terms. So let both S and T have at least 2 terms, and assume the result established for any smaller combined number of terms. By dividing S by c(S) and T by c(T), we reduce to the case c(S) = c(T) = 1. If the contents c = c(ST) is not invertible, it has a non-trivial divisor in common with the leading coefficient of at least one of S and T (since it divides their product, which is the leading coefficient of ST). Suppose by symmetry that this is the case for S, let L be the leading term of S, and let d = gcd(c,c(L)) be the mentioned common divisor (here the contents c(L) of L is just its unique coefficient). Since d is a common divisor of ST and LT, it also divides (S − L)T, in other words it divides its contents, which by induction (since S − L has fewer terms than S) is c(S − L)c(T) = c(S − L). As d also divides c(L), it divides c(S) = 1, which gives a contradiction; therefore c(ST) is invertible (and can be taken to be 1).

Proof of the irreducibility statement

We prove the irreducibility statement in the setting of a GCD domain R. As mentioned above a non-constant polynomial is irreducible in R[X] if and only if it is primitive and not a product of two non-constant polynomials in F[X]. Being irreducible in F[X] certainly excludes the latter possibility (since those non-constant polynomials would remain non-invertible in F[X]), so the essential point left to prove is that if P is non-constant and irreducible in R[X] then it is irreducible in F[X].

Note first that in F[X]\{0} any class of associate elements (whose elements are related by multiplication by nonzero elements of the field F) meets the set of primitive elements in R[X]: starting from an arbitrary element of the class, one can first (if necessary) multiply by a nonzero element of R to enter into the subset R[X] (removing denominators), then divide by the greatest common divisor of all coefficients to obtain a primitive polynomial. Now assume that P is reducible in F[X], so P = ST with S,T non-constant polynomials in F[X]. One can replace S and T by associate primitive elements S′, T′, and obtain P = αS′T′ for some nonzero α in F. But S′T′ is primitive in R[X] by the primitivity statement, so α must lie in R (if α is written as a fraction a/b, then b has to divide all coefficients of aS′T′, so b divides c(aS′T′) = a, which means α = a/b is in R) and the decomposition P = αS′T′ contradicts the irreducibility of P in R[X].

Implications

The first result implies that the contents of polynomials, defined as the GCD of their coefficients, are multiplicative: the contents of the product of two polynomials is the product of their individual contents.

The second result implies that if a polynomial with integer coefficients can be factored over the rational numbers, then there exists a factorization over the integers. This property is also useful when combined with properties such as Eisenstein's criterion.

Both results are essential in proving that if R is a unique factorization domain, then so is R[X] (and by an immediate induction, so is the polynomial ring over R in any number of indeterminates). For any factorization of a polynomial P in R[X], the statements imply that the product Q of all irreducible factors that are not contained in R (the non-constant factors) is always primitive, so P = c(P)Q where c(P) is the contents of P. This reduces proving uniqueness of factorizations to proving it individually for c(P) (which is given) and for Q. By the second statement the irreducible factors in any factorization of Q in R[X] are primitive representatives of irreducible factors in a factorization of Q in F[X], but the latter is unique since F[X] is a principal ideal domain and therefore a unique factorization domain.

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

Notes