Primitive part and content: Difference between revisions

Revision as of 02:36, 12 July 2016

Latest revision as of 06:20, 28 June 2025

(23 intermediate revisions by 11 users not shown)

Line 1:

{{No footnotes|date=December 2018}}

In [[algebra]], the '''content''' of a [[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 (ring theory)|unit]] of the [[ring (mathematics)|ring]] of the coefficients (and the multiplication of the primitive part by the [[multiplicative inverse|inverse]] of the unit).

In [[algebra]], the '''content''' of a nonzero [[polynomial]] with [[integer]] coefficients[[coefficient]]s (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 (ring theory)|unit]] of the [[ring (mathematics)|ring]] of the coefficients (and the multiplication of the primitive part by the [[multiplicative inverse|inverse]] of the unit).

A polynomial is ''[[Primitive polynomial (ring theory)|primitive]]'' if its content equals 1. Thus the primitive part of a polynomial is a primitive polynomial.

A polynomial is ''[[Primitive polynomial (ring theory)|'primitive]]''' if its content equals 1. Thus the primitive part of a polynomial is a primitive polynomial.

[[Gauss's lemma (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[[Gauss's thelemma computation(polynomials)|Gauss's oflemma greatestfor commonpolynomials]] divisorsstates isthat generallythe muchproduct easierof thanprimitive [[polynomialpolynomials factorization]],(with thecoefficients firstin step ofthe asame polynomialunique factorization algorithm___domain) also is generallyprimitive. This implies that the computationcontent ofand itsthe primitive part–contentpart factorizationof (seethe {{slink|Factorizationproduct of two polynomials|Primitive part–contentare, factorization}}). Thenrespectively, the factorizationproduct problemof isthe reducedcontents to factorize separatelyand the contentproduct andof the primitive partparts.

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 {{slink|Factorization of polynomials|Primitive part–content factorization}}). Then the factorization problem is reduced to factorizing separately the content and the primitive part.

Content and primitive part may be generalized to polynomials over the [[rational number]]s, 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.

Content and primitive part may be generalized to polynomials over the [[rational number]]s, and, more generally, to polynomials over the [[field of fractions]] of a unique factorization ___domain. This makes essentially equivalent the problems of computing [[polynomial greatest common divisor|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 <math>-12x^3+30x-20</math> may be either 2 or –2−2, since 2 is the greatest common divisor of –12−12, 30, and -20−20. If one chooses 2 as the content, the primitive part of this polynomial is

:<math>-6x^3+15x-10 = \frac{-12x^3+30x-20}{2},</math>

and thus the primitive–part–contentprimitive-part-content factorization is

:<math>-12x^3+30x-20 = 2 (-6x^3+15x-10).</math>

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

:<math>-12x^3+30x-20 =-2 (6x^3-15x+10).</math>

==Properties==

In the remainingremainder of this article, we consider polynomials over a [[unique factorization ___domain]] {{math|''R''}}, which can typically be the ring of [[integerInteger#Algebraic properties|integers]]s, or a [[polynomial ring]] over a [[field (mathematics)|field]]. In {{math|''R''}}, [[greatestGreatest common divisor#In commutative rings|greatest common divisors]]s are well defined, and are unique [[up to]] the multiplication by a [[unit (ring theory)|unit]] of {{math|''R''}}.

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

:<math display="block">P = c(P) \operatorname{pp}(P),</math>

which is called the primeprimitive-part-content factorization of {{math|''P''}}.

The main properties of the content and the primitive part resultare results of [[Gauss's lemma (polynomial)|Gauss's lemma]], which asserts that the product of two primitive polynomials is primitive, where a polynomial is primitive if 1 is athe greatest common divisor of its coefficients. This implies:

*The content of a product of polynomialpolynomials is the product of their contents: <math display="block">c(P_1 P_2) = c(P_1) c(P_2).</math>

*The primitive part of a product of polynomials is the product of their primitive parts: <math display="block"> \operatorname{pp}(P_1 P_2) = \operatorname{pp}(P_1) \operatorname{pp}(P_2).</math>

::<math>c(P_1P_2)=c(P_1)c(P_2)</math>

*The content of a greatest common divisor of polynomials is the greatest common divisor (in {{math|''R''}}) of their contents: <math display="block"> c(\operatorname{gcd}(P_1, P_2)) = \operatorname{gcd}(c(P_1), c(P_2)).</math>

*The primitive part of a product of polynomials is the product of their primitive parts:

*The primitive part of a greatest common divisor of polynomials is the greatest common divisor (in {{math|''R''}}) of their primitive parts:: <math display="block"> \operatorname{pp}(P_1P_2\operatorname{gcd}(P_1, P_2)) = \operatorname{gcd}(\operatorname{pp}(P_1), \operatorname{pp}(P_2)).</math>

*The content of a greatest common divisor of polynomials is the greatest common divisor (in {{math|''R''}}) of their contents:

::<math>c(\operatorname{gcd}(P_1, P_2))=\operatorname{gcd}(c(P_1), c(P_2))</math>

*The primitive part of a greatest common divisor of polynomials is the greatest common divisor (in {{math|''R''}}) of their primitive parts:

::<math>\operatorname{pp}(\operatorname{gcd}(P_1, P_2))=\operatorname{gcd}(\operatorname{pp}(P_1), \operatorname{pp}(P_2))</math>

*The complete [[factorization of polynomials|factorization]] of a polynomial over {{math|''R''}} is the product of the factorization (in {{math|''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 primeprimitive-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 {{math|''R''}}, which is usually much easier than factorization.

==Over the rationals==

The primitive-part-content factorization may be extended to polynomials with [[rational number|rational]] coefficients as follows.

Given a polynomial {{math|''P''}} with rational coefficients, by rewriting its coefficients with the same [[common denominator]] {{math|''d''}}, one may rewrite {{math|''P''}} as

:<math>P=\frac{Q}{d},</math>

where {{math|Q}} is a polynomial with integer coefficients.

The the '''content''' of {{math|''P''}} is the quotient by {{math|''d''}} of the content of {{math|''Q''}}, that is

:<math>c(P)=\frac{c(Q)}{d},</math>

and the '''primitive part''' of {{math|''P''}} is the primitive part of {{math|''Q''}}:

Line 53 ⟶ 51:

:<math>P=c(P)\operatorname{pp}(P).</math>

This shows that every polynomial over the rationals is [[associate elements|associated]] towith 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 rationalrationals is equivalent to factoring primitive polynomials over the integers. As polynomials with coefficients in a [[field (mathematics)}field]] are more common than polynomials with integer coefficientcoefficients, it may seem that this equivalence may be used for factoring polynomials with integer coefficients. In fact, thisthe truth is exactly the contraryopposite: every known efficient algorithm for factoring polynomials with rational coefficientcoefficients uses this equivalence for reducing the problem [[modular arithmetic|modulo]] some [[prime number]] {{math|''p''}} (see [[Factorization of polynomials]]).

This equivalence is also used for computing [[polynomial greatest common divisor|greatest common divisors]]s 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 [[irreducible fraction|reduced form]] of many fractions, and this makes the Euclidean algorithm less efficient than algorithms which work only with polynomials over the integers (see [[polynomialPolynomial greatest common divisor]]).

==Over a field of fractions==

The results of the preceding section remain valid if the ring of [[Integer#Algebraic properties|integers]] and the field of rationals are respectively replaced by any [[unique factorization ___domain]] {{math|''R''}} and its [[field of fractions]] {{math|''K''}}.

This is typically used for factoring [[multivariate polynomial]]s, and for [[mathematical proof|proving]] that a polynomial ring over a unique factorization ___domain, andis foralso factoringa [[multivariateunique polynomial]]sfactorization ___domain.

===Unique factorization property of polynomial rings===

ForA proving[[polynomial thatring]] over a polynomial[[field ring(mathematics)|field]] overis a unique factorization ___domain. The same is true for a uniquepolynomial ring over a unique factorization ___domain. To prove this, it suffices to consider the [[univariate]] case, as the general case may be deduced by a [[mathematical induction|recurrenceinduction]] on the number of indeterminates.

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

So, let {{math|''R''}} be a unique factorization ___domain, which is not a field, and {{math|''R''[''X'']}} the univariate [[polynomial ring]] over {{math|''R''}}. An irreducible element {{math|''r''}} in {{math|''R''[''X'']}} is either an irreducible element in {{math|''R''}} or an irreducible primitive polynomial.

If {{math|''r''}} is in {{math|''R''}}, and divides a product <math>P_1P_2</math> of two polynomials, andthen does notit divides any of them, then one may consider, in each factor, the firstcontent term<math>c(P_1P_2) that= is not a multiple of {{c(P_1)c(P_2).</math|''r''}}.> TheThus, product of these first terms is not a multiple of {{math|''r''}} (by Euclid's lemma in {{math|''R''}}), andit appearsdivides as a [[summand]] in a termone of the product of polynomialscontents, whoseand alltherefore other terms are multipleone of {{math|''r''}}. This contradicts the hypothesis that {{math|''r''}} divides all terms of the product of polynomials.

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

===Factorization of multivariate polynomials===

{{see also|Factorization of 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 factorizefactorizing separately the primitive part and the content. As the content has one less indeterminate, it may be factorized by applying the method [[recursion (computer science)|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 changeschange the [[degree of a polynomial|degree]] in the remaining variable, factorizing the resulting univariate polynomial, and lifting the result to a factorization of the primitive part.

==See also==

Line 87 ⟶ 85:

* {{cite book | author=B. Hartley | authorlink=Brian Hartley |author2=T.O. Hawkes | title=Rings, modules and linear algebra | publisher=Chapman and Hall | year=1970 | isbn=0-412-09810-5 }}

* Page 181 of {{Lang Algebra|edition=3}}

* {{cite book | author=David Sharpe | title=Rings and factorization | url=https://archive.org/details/ringsfactorizati0000shar | url-access=registration | publisher=[[Cambridge University Press]] | year=1987 | isbn=0-521-33718-6 | pages=[https://archive.org/details/ringsfactorizati0000shar/page/68 68–69] }}

[[Category:Algebra]]