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). This statements have several generalizations described below.

Primitive and irreducible polynomials

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 a commutative ring: 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. If R is an integral domain then so is the polynomial ring R[X] because the leading coefficient of product of non-zero polynomials in R[X] is equal to the product of their leading coefficients, hence is nonzero. A non-constant irreducible polynomial in R[X] 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.

Version valid over integers

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.

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 with a coefficient not divisible by p, respectively in f(x) and in g(x). Now consider the coefficient of x^r+s in the product. Its value is given by ∑a_ib_j, where the sum runs over all pairs of indices i,j such that i + j = r + s. 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.

Alternatively the statement can be proved as a special case of more general results given below.

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].

This is a special case for R = Z of more general irreducibility statement proved below.

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 fact is often useful when combined with results such as Eisenstein's criterion.

An application is the rational root theorem.

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

Version valid over any GCD domain

Gauss's lemma holds more generally over arbitrary GCD 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 class of associate elements).

Primitivity statement: If R is a GCD domain, then the set of primitive polynomials in R[X] is closed under multiplication. More generally content of a product ST of polynomials is the product c(S)c(T) of their contents.

Proof:^[1] The latter part follows from the former 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. For the proof of the former part 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 content 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 content 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 content, 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).

Irreducibility statement: Let R be a GCD domain 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].

Proof: 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 R[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].

The condition that R is a GCD 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²X² = q(b + (p+a)X + qX²) shows the failure of the primitivity statement. For a concrete example one can take R = Z[i√5], p = 1 + i√5, a = 1 - i√5, q = 2, b = 3. 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[i√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.

In the special case when R is unique factorization domain (UFD), the primitivity statement can be proved more easily:

Proof: Let S,T be primitive polynomials in R[X], and assume that their product ST is not primitive, so that some non-invertible element d of R divides all coefficients of ST. There is some irreducible element p of R that divides d (this is where we use that R is UFD, if R was only GCD domain then such element wouldn't necessarily exist), and it is also a prime element in R (since R is GCD domain). 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 (because nonzero polynomials over an integral domain cannot be zero divisors by consideration of the leading coefficient of their product). By hypothesis the projection R[X]→(R/pR)[X] sends ST to 0, and since this is the product of the projections of S and T (projection is a ring homomorphism), at least one of those projections is 0 (here one uses that (R/pR)[X] is an integral domain). But this means that p divides all of the coefficients either of S or of T, which contradicts its assumed primitivity.

This special case is also sufficient in many applications. For example both primitivity and irreducibility statement for UFD are essential in proving that if R is UFD, then so is R[X] (and by an immediate induction, so is the polynomial ring over R in any number of indeterminates). Any factorization of a polynomial P in R[X] can be split into its irreducible factors that are contained in R (the "constant" factors) and those that are not. The primitivity statement implies that the product Q of the latter (non-constant) irreducible factors is primitive, so the product of the former (constant) factors give the content c(P) of P. This reduces proving uniqueness of factorizations to proving it individually for c(P) and for Q. Since the factorization of c(P) takes place in R, it is unique by assumption. By the irreducibility statement, the irreducible factors that occur 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. Together this shows that the factorization of P in R[X] is unique.

Version valid over arbitrary commutative ring

As explained above, neither primitivity nor irreducibility statement of Gauss's lemma is valid over general integral domains. However there is a variation of the first statement that is valid even for polynomials over any commutative ring R, which replaces primitivity by the stronger property of co-maximality. 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. Clearly every co-maximal polynomial in R[X] is primitive. If R is a Bézout domain (so in particular if it's a principal ideal domain) then also every primitive polynomial in R is co-maximal. However co-maximality is often much more restrictive condition than primitivity even when R is UFD. For example let k be a field and R = k[Y,Z], which is UFD as explained above. Then the polynomial P = Y + ZX is primitive but not co-maximal in R[X] because the ideal (Y,Z) in R generated by the coefficients of P is proper (primitivity simply means that this ideal isn't contained in any proper principal ideal). We have the following variation of Gauss's lemma:

Co-maximality statement: Let R be a commutative ring. Then the product of two co-maximal polynomials in R[X] 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, thus 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.

Notes