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 ...
, the content of a
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
with
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
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 var ...
s (or, more generally, with coefficients in 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 an ...
) is the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of its coefficients. The primitive part of such a polynomial is the quotient of the polynomial by its content. Thus a polynomial is the product of its primitive part and its content, and this factorization is unique
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
the multiplication of the content by a
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (alb ...
of the
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 ...
of the coefficients (and the multiplication of the primitive part by the
inverse
Inverse or invert may refer to:
Science and mathematics
* Inverse (logic), a type of conditional sentence which is an immediate inference made from another conditional sentence
* Additive inverse (negation), the inverse of a number that, when ad ...
of the unit).
A polynomial is primitive if its content equals 1. Thus the primitive part of a polynomial is a primitive polynomial.
Gauss's lemma for polynomials states that the product of primitive polynomials (with coefficients in the same unique factorization domain) also is primitive. This implies that the content and the primitive part of the product of two polynomials are, respectively, the product of the contents and the product of the primitive parts.
As the computation of greatest common divisors is generally much easier than
polynomial factorization
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field (mathematics), field or in the integers as the product of irreducible polynomial, irreducible ...
, the first step of a polynomial factorization algorithm is generally the computation of its primitive part–content factorization (see ). Then the factorization problem is reduced to factorize separately the content and the primitive part.
Content and primitive part may be generalized to polynomials over the
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
s, and, more generally, to polynomials over the
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 a unique factorization domain. This makes essentially equivalent the problems of computing
greatest common divisors and factorization of polynomials over the integers and of polynomials over the rational numbers.
Over the integers
For a polynomial with integer coefficients, the content may be either the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
of the coefficients or its
additive inverse
In mathematics, the additive inverse of a number is the number that, when added to , yields zero. This number is also known as the opposite (number), sign change, and negation. For a real number, it reverses its sign: the additive inverse (opp ...
. The choice is arbitrary, and may depend on a further convention, which is commonly that the
leading 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 var ...
of the primitive part be positive.
For example, the content of
may be either 2 or −2, since 2 is the greatest common divisor of −12, 30, and −20. If one chooses 2 as the content, the primitive part of this polynomial is
:
and thus the primitive-part-content factorization is
:
For aesthetic reasons, one often prefers choosing a negative content, here −2, giving the primitive-part-content factorization
:
Properties
In the remainder of this article, we consider polynomials 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 an ...
, which can typically be the ring of
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
, or a
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
over 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 ...
. In ,
greatest common divisors are well defined, and are unique up to multiplication by a
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (alb ...
of .
The content of a polynomial with coefficients in is the greatest common divisor of its coefficients, and, as such, is defined up to multiplication by a unit. The primitive part of is the quotient of by its content; it is a polynomial with coefficients in , which is unique up to multiplication by a unit. If the content is changed by multiplication by a unit , then the primitive part must be changed by dividing it by the same unit, in order to keep the equality
:
which is called the primitive-part-content factorization of .
The main properties of the content and the primitive part are results of
Gauss's lemma Gauss's lemma can mean any of several lemmas named after Carl Friedrich Gauss:
*
*
*
* A generalization of Euclid's lemma is sometimes called Gauss's lemma
See also
* List of topics named after Carl Friedrich Gauss
Carl Friedrich Gauss ( ...
, which asserts that the product of two primitive polynomials is primitive, where a polynomial is primitive if 1 is the greatest common divisor of its coefficients. This implies:
*The content of a product of polynomials is the product of their contents:
::
*The primitive part of a product of polynomials is the product of their primitive parts:
::
*The content of a greatest common divisor of polynomials is the greatest common divisor (in ) of their contents:
::
*The primitive part of a greatest common divisor of polynomials is the greatest common divisor (in ) of their primitive parts:
::
*The complete
factorization
In mathematics, factorization (or factorisation, see American and British English spelling differences#-ise, -ize (-isation, -ization), English spelling differences) or factoring consists of writing a number or another mathematical object as a p ...
of a polynomial over is the product of the factorization (in ) of the content and of the factorization (in the polynomial ring) of the primitive part.
The last property implies that the computation of the primitive-part-content factorization of a polynomial reduces the computation of its complete factorization to the separate factorization of the content and the primitive part. This is generally interesting, because the computation of the prime-part-content factorization involves only greatest common divisor computation in , which is usually much easier than factorization.
Over the rationals
The primitive-part-content factorization may be extended to polynomials with rational coefficients as follows.
Given a polynomial with rational coefficients, by rewriting its coefficients with the same
common denominator
In mathematics, the lowest common denominator or least common denominator (abbreviated LCD) is the lowest common multiple of the denominators of a set of fractions. It simplifies adding, subtracting, and comparing fractions.
Description
The low ...
, one may rewrite as
:
where is a polynomial with integer coefficients.
The content of is the quotient by of the content of , that is
:
and the primitive part of is the primitive part of :
:
It is easy to show that this definition does not depend on the choice of the common denominator, and that the primitive-part-content factorization remains valid:
:
This shows that every polynomial over the rationals is
associated Associated may refer to:
*Associated, former name of Avon, Contra Costa County, California
* Associated Hebrew Schools of Toronto, a school in Canada
*Associated Newspapers, former name of DMG Media, a British publishing company
See also
*Associati ...
with a unique primitive polynomial over the integers, and that the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
allows the computation of this primitive polynomial.
A consequence is that factoring polynomials over the rationals is equivalent to factoring primitive polynomials over the integers. As polynomials with coefficients in a field are more common than polynomials with integer coefficients, it may seem that this equivalence may be used for factoring polynomials with integer coefficients. In fact, the truth is exactly the opposite: every known efficient algorithm for factoring polynomials with rational coefficients uses this equivalence for reducing the problem
modulo
In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation).
Given two positive numbers and , modulo (often abbreviated as ) is t ...
some
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
(see
Factorization of polynomials
In mathematics and computer algebra, factorization of polynomials or polynomial factorization expresses a polynomial with coefficients in a given field or in the integers as the product of irreducible factors with coefficients in the same dom ...
).
This equivalence is also used for computing greatest common divisors of polynomials, although the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
is defined for polynomials with rational coefficients. In fact, in this case, the Euclidean algorithm requires one to compute the
reduced form In statistics, and particularly in econometrics, the reduced form of a system of equations is the result of solving the system for the endogenous variables. This gives the latter as functions of the exogenous variables, if any. In econometrics, the ...
of many fractions, and this makes the Euclidean algorithm less efficient than algorithms which work only with polynomials over the integers (see
Polynomial greatest common divisor
In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials. This concept is analogous to the greatest common di ...
).
Over a field of fractions
The results of the preceding section remain valid if the ring of
integers
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language o ...
and the field of rationals are respectively replaced by any
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 an ...
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 ...
.
This is typically used for factoring
multivariate polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
s, and for
proving that a polynomial ring over a unique factorization domain is also a unique factorization domain.
Unique factorization property of polynomial rings
A
polynomial ring
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variables) ...
over 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 ...
is a unique factorization domain. The same is true for a polynomial ring over a unique factorization domain. To prove this, it suffices to consider the
univariate
In mathematics, a univariate object is an expression, equation, function or polynomial involving only one variable. Objects involving more than one variable are multivariate. In some cases the distinction between the univariate and multivariate cas ...
case, as the general case may be deduced by
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
on the number of indeterminates.
The unique factorization property is a direct consequence of
Euclid's lemma
In algebra and number theory, Euclid's lemma is a lemma that captures a fundamental property of prime numbers, namely:
For example, if , , , then , and since this is divisible by 19, the lemma implies that one or both of 133 or 143 must be as w ...
: If 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 ...
divides a product, then it divides one of the factors. For univariate polynomials over a field, this results from
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they a ...
, which itself results from the
Euclidean algorithm
In mathematics, the Euclidean algorithm,Some widely used textbooks, such as I. N. Herstein's ''Topics in Algebra'' and Serge Lang's ''Algebra'', use the term "Euclidean algorithm" to refer to Euclidean division or Euclid's algorithm, is an effi ...
.
So, let be a unique factorization domain, which is not a field, and the univariate polynomial ring over . An irreducible element in is either an irreducible element in or an irreducible primitive polynomial.
If is in and divides a product
of two polynomials, then it divides the content
Thus, by Euclid's lemma in , it divides one of the contents, and therefore one of the polynomials.
If is not , it is a primitive polynomial (because it is irreducible). Then Euclid's lemma in results immediately from Euclid's lemma in , where is the field of fractions of .
Factorization of multivariate polynomials
For factoring a multivariate polynomial over a field or over the integers, one may consider it as a univariate polynomial with coefficients in a polynomial ring with one less indeterminate. Then the factorization is reduced to factorizing separately the primitive part and the content. As the content has one less indeterminate, it may be factorized by applying the method
recursively
Recursion (adjective: ''recursive'') occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in mathematics ...
. For factorizing the primitive part, the standard method consists of substituting integers to the indeterminates of the coefficients in a way that does not change the
degree
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
in the remaining variable, factorizing the resulting univariate polynomial, and lifting the result to a factorization of the primitive part.
See also
*
Rational root theorem
In algebra, the rational root theorem (or rational root test, rational zero theorem, rational zero test or theorem) states a constraint on rational solutions of a polynomial equation
:a_nx^n+a_x^+\cdots+a_0 = 0
with integer coefficients a_i\in\m ...
References
*
* Page 181 of
* {{cite book , author=David Sharpe , title=Rings and factorization , url=https://archive.org/details/ringsfactorizati0000shar , url-access=registration , publisher=
Cambridge University Press
Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press
A university press is an academic publishing hou ...
, year=1987 , isbn=0-521-33718-6 , page
68–69
Algebra
Polynomials