Utilisateur:Dfeldmann/brouillon2

⇐ brouillon précédent Ceci est un brouillon de traduction ; prière de ne pas le modifier ⇒ brouillon suivant

En algèbre, le contenu d'un polynôme non nul à coefficients entiers (ou, plus généralement, à coefficients dans un anneau factoriel) est le plus grand commun diviseur de ses coefficients. La partie primitive d'un tel polynôme est le quotient du polynôme par son contenu. Ainsi, un polynôme est le produit de sa partie primitive et de son contenu, et cette factorisation est unique à un multiple près du contenu par une unité de l'anneau des coefficients (et à la multiplication de la partie primitive par l'inverse de cette unité).

Un polynôme est primitif si son contenu est égal à 1. Ainsi, la partie primitive d'un polynôme est un polynôme primitif.

Le lemme de Gauss pour les polynômes affirme que le produit de polynômes primitifs (ayant des coefficients dans le même anneau factoriel) est aussi primitif. Cela implique que le contenu et la partie primitive du produit de deux polynômes sont respectivement le produit des contenus et le produit des parties primitives.

Comme le calcul des plus grands communs diviseurs est généralement beaucoup plus facile que la factorisation des polynômes, la première étape d'un algorithme de factorisation de polynômes est généralement le calcul de la factorisation en partie primitive et contenu. Ensuite, le problème de factorisation se réduit à factoriser séparément le contenu et la partie primitive.

Le contenu et la partie primitive peuvent être généralisés aux polynômes à coefficients rationnels et, plus généralement, aux polynômes à coefficients dans le corps des fractions d'un anneau factoriel. Cela ramène essentiellement les problèmes de factorisation de polynômes sur les entiers et sur les nombres rationnels à des problèmes de calcul de plus grand commun diviseur entre polynômes (en).

Sur les entiers[modifier | modifier le code]

Pour un polynôme à coefficients entiers, le contenu peut être soit le plus grand commun diviseur des coefficients, soit son opposé. Le choix est arbitraire et peut dépendre d'une convention supplémentaire, qui est couramment que le coefficient directeur de la partie primitive soit positif. Par exemple, le contenu de $-12x^{3}+30x-20$ peut être soit 2, soit -2, puisque 2 est le plus grand commun diviseur de -12, 30 et -20. Si l'on choisit 2 comme contenu, la partie primitive de ce polynôme est : $-6x^{3}+15x-10={\frac {-12x^{3}+30x-20}{2}},$ et donc la factorisation partie primitive et contenu est : $-12x^{3}+30x-20=2(-6x^{3}+15x-10).$ Pour des raisons esthétiques, on préfère souvent choisir un contenu négatif, ici -2, donnant la factorisation partie primitive et contenu : $-12x^{3}+30x-20=-2(6x^{3}-15x+10).$

Propriétés[modifier | modifier le code]

Dans la suite de cet article, nous considérons les polynômes sur un anneau de factorisation unique $R$ , qui peut typiquement être l'anneau des entiers, ou un anneau de polynômes sur un corps. Dans $R$ , les plus grands communs diviseurs sont bien définis et sont uniques à un multiple près par une unité de $R$ . Le contenu $c (P)$ d'un polynôme $P$ à coefficients dans $R$ est le plus grand commun diviseur de ses coefficients et, comme tel, est défini à un multiple près par une unité. La partie primitive $pp(P)$ de $P$ est le quotient $P / c (P)$ de $P$ par son contenu; c'est un polynôme à coefficients dans $R$ , qui est unique à un multiple près par une unité. Si le contenu est modifié par multiplication par une unité $u$ , alors la partie primitive doit être modifiée en la divisant par la même unité, afin de maintenir l'égalité

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

qui est appelée la factorisation partie primitive-contenu de

P

. Les principales propriétés du contenu et de la partie primitive sont des résultats du lemme de Gauss, qui affirme que le produit de deux polynômes primitifs est primitif, où un polynôme est primitif si 1 est le plus grand commun diviseur de ses coefficients. Cela implique : Le contenu du produit de polynômes est le produit de leurs contenus :

c(P_{1}P_{2})=c(P_{1})c(P_{2}).

La partie primitive du produit de polynômes est le produit de leurs parties primitives :

\operatorname {pp} (P_{1}P_{2})=\operatorname {pp} (P_{1})\operatorname {pp} (P_{2}).

Le contenu d'un plus grand commun diviseur de polynômes est le plus grand commun diviseur (dans

R

) de leurs contenus :

c(\operatorname {gcd} (P_{1},P_{2}))=\operatorname {gcd} (c(P_{1}),c(P_{2})).

La partie primitive d'un plus grand commun diviseur de polynômes est le plus grand commun diviseur (dans

R

) de leurs parties primitives :

\operatorname {pp} (\operatorname {gcd} (P_{1},P_{2}))=\operatorname {gcd} (\operatorname {pp} (P_{1}),\operatorname {pp} (P_{2})).

La factorisation complète d'un polynôme sur

R

est le produit de la factorisation (dans

R

) du contenu et de la factorisation (dans l'anneau de polynômes) de la partie primitive. La dernière propriété implique que le calcul de la factorisation partie primitive-contenu d'un polynôme réduit le calcul de sa factorisation complète à la factorisation séparée du contenu et de la partie primitive. Cela est généralement intéressant, car le calcul de la factorisation partie primitive-contenu implique seulement le calcul des plus grands communs diviseurs dans

R

, ce qui est généralement beaucoup plus facile que la factorisation.

Sur les rationnels[modifier | modifier le code]

La factorisation partie primitive-contenu peut être étendue aux polynômes à coefficients rationnels comme suit. Étant donné un polynôme $P$ à coefficients rationnels, en réécrivant ses coefficients avec le même dénominateur commun $d$ , on peut réécrire $P$ comme : $P={\frac {Q}{d}},$ où $Q$ est un polynôme à coefficients entiers. Le contenu de $P$ est le quotient par $d$ du contenu de $Q$ , c'est-à-dire : $c(P)={\frac {c(Q)}{d}},$ et la partie primitive de $P$ est la partie primitive de $Q$ : : $\operatorname {pp} (P)=\operatorname {pp} (Q).$ Il est facile de montrer que cette définition ne dépend pas du choix du dénominateur commun et que la factorisation partie primitive-contenu reste valide : : $P=c(P)\operatorname {pp} (P).$ Cela montre que chaque polynôme sur les rationnels est associé à un polynôme primitif unique sur les entiers et que l'algorithme d'Euclide permet de calculer ce polynôme primitif. Une conséquence est que la factorisation des polynômes sur les rationnels équivaut à la factorisation des polynômes primitifs sur les entiers. Comme les polynômes à coefficients dans un corps sont plus courants que les polynômes à coefficients entiers, il peut sembler que cette équivalence puisse être utilisée pour factoriser des polynômes à coefficients entiers. En fait, la vérité est exactement l'inverse : chaque algorithme efficace connu pour factoriser des polynômes à coefficients rationnels utilise cette équivalence pour réduire le problème modulo un certain nombre premier $p$ (voir Factorisation des polynômes). Cette équivalence est également utilisée pour calculer les plus grands communs diviseurs de polynômes, bien que l'algorithme d'Euclide soit défini pour les polynômes à coefficients rationnels. En fait, dans ce cas, l'algorithme d'Euclide nécessite de calculer la forme réduite de nombreuses fractions, ce qui rend l'algorithme d'Euclide moins efficace que les algorithmes qui ne travaillent qu'avec des polynômes sur les entiers (voir Plus grand commun diviseur de polynômes).

Sur un corps de fractions[modifier | modifier le code]

Les résultats de la section précédente restent valides si l'anneau des entiers et le corps des rationnels sont respectivement remplacés par un anneau de factorisation unique $R$ et son corps de fractions $K$ . Cela est typiquement utilisé pour factoriser des polynômes multivariés et pour prouver qu'un anneau de polynômes sur un anneau de factorisation unique est également un anneau de factorisation unique.

Propriété de factorisation unique des anneaux de polynômes[modifier | modifier le code]

Un anneau de polynômes sur un corps est un anneau de factorisation unique. Il en est de même pour un anneau de polynômes sur un anneau de factorisation unique. Pour prouver cela, il suffit de considérer le cas univarié, car le cas général peut être déduit par induction sur le nombre d'indéterminées. La propriété de factorisation unique est une conséquence directe du Lemme d'Euclide : Si un élément irréductible divise un produit, alors il divise l'un des facteurs. Pour les polynômes univariés sur un corps, cela résulte de l'identité de Bézout, qui elle-même résulte de l'algorithme d'Euclide. Ainsi, soit $R$ un anneau de factorisation unique, qui n'est pas un corps, et $R [X]$ l'anneau de polynômes univariés sur $R$ . Un élément irréductible $r$ dans $R [X]$ est soit un élément irréductible dans $R$ , soit un polynôme primitif irréductible. Si $r$ est dans $R$ et divise un produit $P_{1}P_{2}$ de deux polynômes, alors il divise le contenu $c(P_{1}P_{2})=c(P_{1})c(P_{2}).$ Ainsi, par le lemme d'Euclide dans $R$ , il divise l'un des contenus, et donc l'un des polynômes. Si $r$ n'est pas dans $R$ , c'est un polynôme primitif (parce qu'il est irréductible). Alors le lemme d'Euclide dans $R [X]$ résulte immédiatement du lemme d'Euclide dans $K [X]$ , où $K$ est le corps de fractions de $R$ .

Factorisation des polynômes multivariés[modifier | modifier le code]

Article connexe : Factorisation des polynômes.

Pour factoriser un polynôme multivarié sur un corps ou sur les entiers, on peut le considérer comme un polynôme univarié à coefficients dans un anneau de polynômes avec une indéterminée en moins. Ensuite, la factorisation est réduite à la factorisation séparée de la partie primitive et du contenu. Comme le contenu a une indéterminée en moins, il peut être factorisé en appliquant la méthode récursivement. Pour factoriser la partie primitive, la méthode standard consiste à substituer des entiers aux indéterminées des coefficients de manière à ne pas changer le degré dans la variable restante, à factoriser le polynôme univarié résultant et à élever le résultat à une factorisation de la partie primitive.

Voir aussi[modifier | modifier le code]

*Théorème des racines rationnelles

Références[modifier | modifier le code]

(en) B. Hartley et T.O. Hawkes, Rings, modules and linear algebra, Chapman and Hall, 1970 (ISBN 0-412-09810-5) Page 181 de Modèle:Lang Algebra (en) David Sharpe, Rings and factorization, Cambridge University Press, 1987, 68–69 (ISBN 0-521-33718-6, lire en ligne)

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

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, the first step of a polynomial factorization algorithm is generally the computation of its primitive part–content factorization (see Modèle:Slink). 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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Article connexe : 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 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.

References[modifier | modifier le code]

(en) B. Hartley et T.O. Hawkes, Rings, modules and linear algebra, Chapman and Hall, 1970 (ISBN 0-412-09810-5)
Page 181 of Modèle:Lang Algebra
(en) David Sharpe, Rings and factorization, Cambridge University Press, 1987, 68–69 (ISBN 0-521-33718-6, lire en ligne)