In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
, Gauss's lemma, named after
Carl Friedrich Gauss
Johann Carl Friedrich Gauss (; german: Gauß ; la, Carolus Fridericus Gauss; 30 April 177723 February 1855) was a German mathematician and physicist who made significant contributions to many fields in mathematics and science. Sometimes refer ...
, is a statement
[This theorem is called a lemma for historical reasons.] about
polynomials over the
integers, or, more generally, over a
unique factorization domain
In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
(that is, a
ring
Ring may refer to:
* Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry
* To make a sound with a bell, and the sound made by a bell
:(hence) to initiate a telephone connection
Arts, entertainment and media Film and ...
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
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
s is ''primitive'' if it has 1 as a
greatest common divisor of its coefficients).
A
corollary
In mathematics and logic, a corollary ( , ) is a theorem of less importance which can be readily deduced from a previous, more notable statement. A corollary could, for instance, be a proposition which is incidentally proved while proving another ...
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 , "rational numbers" must be replaced by "
field of fractions
In abstract algebra, the field of fractions of an integral domain is the smallest field in which it can be embedded. The construction of the field of fractions is modeled on the relationship between the integral domain of integers and the field ...
of ". This implies that, if is either a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
, the ring of integers, or a unique factorization domain, then every
polynomial ring (in one or several indeterminates) over 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
In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural se ...
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
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not ...
.
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
In mathematics, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element. More generally, a principal ideal ring is a nonzero commutative ring whose ideals are princi ...
, there are polynomials that are primitive in the above sense and not primitive in this new sense.
The lemma over the integers
If
is a polynomial with integer coefficients, then
is called ''
primitive'' if the greatest common divisor of all the coefficients
is 1; in other words, no
prime number divides all the coefficients.
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 ''f''(''x'') not divisible by ''p'' and let ''b''
''s''''x''
''s'' be the first term of ''g''(''x'') not divisible by ''p''. Now consider the term ''x''
''r''+''s'' in the product, whose coefficient is
:
The term ''a''
''r''''b''
''s'' 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.
The proof is given below for the more general case. Note that an
irreducible element
In algebra, an irreducible element of a domain is a non-zero element that is not invertible (that is, is not a unit), and is not the product of two non-invertible elements.
Relationship with prime elements
Irreducible elements should not be confus ...
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.
Statements for unique factorization domains
Gauss's lemma holds more generally over arbitrary
unique factorization domain
In mathematics, a unique factorization domain (UFD) (also sometimes called a factorial ring following the terminology of Bourbaki) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is ...
s. There the ''
content
Content or contents may refer to:
Media
* Content (media), information or experience provided to audience or end-users by publishers or media producers
** Content industry, an umbrella term that encompasses companies owning and providing mas ...
'' of a polynomial can be defined as the
greatest common divisor of the coefficients of (like the gcd, the content is actually a set of
associate elements
In mathematics, specifically abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero. Integral domains are generalizations of the ring of integers and provide a natural se ...
). A polynomial with coefficients in a UFD is then said to be primitive if the only elements of that divide all coefficients of at once are the
invertible elements of ; i.e., the gcd of the coefficients is one.
Primitivity statement: If is a UFD, then the set of primitive polynomials in is closed under multiplication. More generally, the content of a product
of polynomials is the product
of their individual contents.
Irreducibility statement: Let be a unique factorization domain and its
field of fractions
In abstract algebra, the field of fractions of an integral domain is the smallest field in which it can be embedded. The construction of the field of fractions is modeled on the relationship between the integral domain of integers and the field ...
. A non-constant polynomial
in