Primitive part and content

Last updated March 06, 2023

In algebra, the content of a nonzero polynomial with integer coefficients (or, more generally, with coefficients in a unique factorization domain) is the greatest common divisor 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 the multiplication of the content by a unit of the ring of the coefficients (and the multiplication of the primitive part by the inverse of the unit).

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, the first step of a polynomial factorization algorithm is generally the computation of its primitive part–content factorization (see Factorization of polynomials § Primitive part–content factorization). 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 numbers, and, more generally, to polynomials over the field of fractions 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 of the coefficients or its additive inverse. The choice is arbitrary, and may depend on a further convention, which is commonly that the leading coefficient of the primitive part be positive.

For example, the content of $-12x^{3}+30x-20$ 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

-6x^{3}+15x-10={\frac {-12x^{3}+30x-20}{2}},

and thus the primitive-part-content factorization is

-12x^{3}+30x-20=2(-6x^{3}+15x-10).

For aesthetic reasons, one often prefers choosing a negative content, here −2, giving the primitive-part-content factorization

-12x^{3}+30x-20=-2(6x^{3}-15x+10).

Properties

In the remainder of this article, we consider polynomials over a unique factorization domain $R$ , which can typically be the ring of integers, or a polynomial ring over a field. In $R$ , greatest common divisors are well defined, and are unique up to multiplication by a unit of $R$ .

The content $c (P)$ of a polynomial $P$ with coefficients in $R$ is the greatest common divisor of its coefficients, and, as such, is defined up to multiplication by a unit. The primitive part $pp(P)$ of $P$ is the quotient $P / c (P)$ of $P$ by its content; it is a polynomial with coefficients in $R$ , which is unique up to multiplication by a unit. If the content is changed by multiplication by a unit $u$ , then the primitive part must be changed by dividing it by the same unit, in order to keep the equality

P=c(P)\operatorname {pp} (P),

which is called the primitive-part-content factorization of $P$ .

The main properties of the content and the primitive part are results of Gauss's lemma, 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: $c(P_{1}P_{2})=c(P_{1})c(P_{2}).$
The primitive part of a product of polynomials is the product of their primitive parts: $\operatorname {pp} (P_{1}P_{2})=\operatorname {pp} (P_{1})\operatorname {pp} (P_{2}).$
The content of a greatest common divisor of polynomials is the greatest common divisor (in $R$ ) of their contents: $c(\operatorname {gcd} (P_{1},P_{2}))=\operatorname {gcd} (c(P_{1}),c(P_{2})).$
The primitive part of a greatest common divisor of polynomials is the greatest common divisor (in $R$ ) of their primitive parts: $\operatorname {pp} (\operatorname {gcd} (P_{1},P_{2}))=\operatorname {gcd} (\operatorname {pp} (P_{1}),\operatorname {pp} (P_{2})).$
The complete factorization of a polynomial over $R$ is the product of the factorization (in $R$ ) 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 $R$ , 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 $P$ with rational coefficients, by rewriting its coefficients with the same common denominator $d$ , one may rewrite $P$ as

P={\frac {Q}{d}},

where $Q$ is a polynomial with integer coefficients. The content of $P$ is the quotient by $d$ of the content of $Q$ , that is

c(P)={\frac {c(Q)}{d}},

and the primitive part of $P$ is the primitive part of $Q$ :

\operatorname {pp} (P)=\operatorname {pp} (Q).

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:

P=c(P)\operatorname {pp} (P).

This shows that every polynomial over the rationals is associated with a unique primitive polynomial over the integers, and that the Euclidean algorithm 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 some prime number $p$ (see Factorization of polynomials).

This equivalence is also used for computing greatest common divisors of polynomials, although the Euclidean algorithm is defined for polynomials with rational coefficients. In fact, in this case, the Euclidean algorithm requires one to compute the reduced form 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).

Over a field of fractions

The results of the preceding section remain valid if the ring of integers and the field of rationals are respectively replaced by any unique factorization domain $R$ and its field of fractions $K$ .

This is typically used for factoring multivariate polynomials, 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 over a field 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 case, as the general case may be deduced by induction on the number of indeterminates.

The unique factorization property is a direct consequence of Euclid's lemma: If an irreducible element divides a product, then it divides one of the factors. For univariate polynomials over a field, this results from Bézout's identity, which itself results from the Euclidean algorithm.

So, let $R$ be a unique factorization domain, which is not a field, and $R [X]$ the univariate polynomial ring over $R$ . An irreducible element $r$ in $R [X]$ is either an irreducible element in $R$ or an irreducible primitive polynomial.

If $r$ is in $R$ and divides a product $P_{1}P_{2}$ of two polynomials, then it divides the content $c(P_{1}P_{2})=c(P_{1})c(P_{2}).$ Thus, by Euclid's lemma in $R$ , it divides one of the contents, and therefore one of the polynomials.

If $r$ is not $R$ , it is a primitive polynomial (because it is irreducible). Then Euclid's lemma in $R [X]$ results immediately from Euclid's lemma in $K [X]$ , where $K$ is the field of fractions of $R$ .

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. 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 in the remaining variable, factorizing the resulting univariate polynomial, and lifting the result to a factorization of the primitive part.

Related Research Articles

In mathematics, Bézout's identity, named after Étienne Bézout, is the following theorem:

In mathematics, more specifically in ring theory, a Euclidean domain is an integral domain that can be endowed with a Euclidean function which allows a suitable generalization of the Euclidean division of integers. This generalized Euclidean algorithm can be put to many of the same uses as Euclid's original algorithm in the ring of integers: in any Euclidean domain, one can apply the Euclidean algorithm to compute the greatest common divisor of any two elements. In particular, the greatest common divisor of any two elements exists and can be written as a linear combination of them. Also every ideal in a Euclidean domain is principal, which implies a suitable generalization of the fundamental theorem of arithmetic: every Euclidean domain is a unique factorization domain.

In mathematics, the Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor (GCD) of two integers (numbers), the largest number that divides them both without a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in his Elements . It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.

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 denoted $. For example, the GCD of 8 and 12 is 4, that is, .$

In arithmetic and number theory, the least common multiple, lowest common multiple, or smallest common multiple of two integers a and b, usually denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero. However, some authors define lcm(a,0) as 0 for all a, since 0 is the only common multiple of a and 0.

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 principal, although some authors refer to PIDs as principal rings. The distinction is that a principal ideal ring may have zero divisors whereas a principal ideal domain cannot.

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers. The Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as $or$

In mathematics, a unique factorization domain (UFD) is a ring in which a statement analogous to the fundamental theorem of arithmetic holds. Specifically, a UFD is an integral domain in which every non-zero non-unit element can be written as a product of prime elements, uniquely up to order and units.

<span class="mw-page-title-main">Factorization</span> (Mathematical) decomposition into a product

In mathematics, factorization (or factorisation, see English spelling differences) or factoring consists of writing a number or another mathematical object as a product of several factors, usually smaller or simpler objects of the same kind. For example, $3 \times 5$ is a factorization of the integer $15$ , and $(x - 2)(x + 2)$ is a factorization of the polynomial $x 2 - 4$ .

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that

In mathematics, an irreducible polynomial is, roughly speaking, a polynomial that cannot be factored into the product of two non-constant polynomials. The property of irreducibility depends on the nature of the coefficients that are accepted for the possible factors, that is, the field to which the coefficients of the polynomial and its possible factors are supposed to belong. For example, the polynomial $x 2 - 2$ is a polynomial with integer coefficients, but, as every integer is also a real number, it is also a polynomial with real coefficients. It is irreducible if it is considered as a polynomial with integer coefficients, but it factors as $if it is considered as a polynomial with real coefficients. One says that the polynomial x 2 - 2 is irreducible over the integers but not over the reals.$

In algebra, a monic polynomial is a non-zero univariate polynomial in which the leading coefficient is equal to 1. That is to say, a monic polynomial is one that can be written as

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients, which is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.

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. Gauss's lemma underlies all the theory of factorization and greatest common divisors of such polynomials.

In mathematics, a GCD domain is an integral domain R with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated by two given elements. Equivalently, any two elements of R have a least common multiple (LCM).

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 domain. Polynomial factorization is one of the fundamental components of computer algebra systems.

In mathematics, a square-free polynomial is a polynomial defined over a field that does not have as a divisor any square of a non-constant polynomial. A univariate polynomial is square free if and only if it has no multiple root in an algebraically closed field containing its coefficients. This motivates that, in applications in physics and engineering, a square-free polynomial is commonly called a polynomial with no repeated roots.

In algebra, the greatest common divisor 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 divisor of two integers.

In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

References

B. Hartley; T.O. Hawkes (1970). Rings, modules and linear algebra. Chapman and Hall. ISBN 0-412-09810-5.
Page 181 of Lang, Serge (1993), Algebra (Third ed.), Reading, Mass.: Addison-Wesley, ISBN 978-0-201-55540-0, Zbl 0848.13001
David Sharpe (1987). Rings and factorization . Cambridge University Press. pp. 68–69. ISBN 0-521-33718-6.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.