Plus grand diviseur commun polynomial - Polynomial greatest common divisor

En algèbre, le plus grand diviseur commun (souvent abrégé en PGCD) de deux polynômes est un polynôme, du plus haut degré possible, qui est un facteur des deux polynômes originaux. Ce concept est analogue au plus grand diviseur commun de deux nombres entiers.

Dans le cas important des polynômes univariés sur un corps, le PGCD polynomial peut être calculé, comme pour le PGCD entier, par l' algorithme d'Euclide utilisant la division longue . Le GCD polynôme est défini uniquement à la multiplication par une constante inversible.

La similitude entre le PGCD entier et le PGCD polynomial permet d'étendre aux polynômes univariés toutes les propriétés qui peuvent être déduites de l'algorithme euclidien et de la division euclidienne . De plus, le polynôme GCD possède des propriétés spécifiques qui en font une notion fondamentale dans divers domaines de l'algèbre. En règle générale, les racines du PGCD de deux polynômes sont les racines communes des deux polynômes, ce qui fournit des informations sur les racines sans les calculer. Par exemple, les racines multiples d'un polynôme sont les racines du PGCD du polynôme et de sa dérivée, et d'autres calculs PGCD permettent de calculer la factorisation sans carré du polynôme, qui fournit des polynômes dont les racines sont les racines d'une multiplicité donnée de le polynôme d'origine.

Le plus grand commun diviseur peut être défini et existe, plus généralement, pour des polynômes multivariés sur un corps ou l'anneau d'entiers, et aussi sur un domaine de factorisation unique . Il existe des algorithmes pour les calculer dès qu'on a un algorithme GCD dans l'anneau des coefficients. Ces algorithmes procèdent par récursivité sur le nombre de variables pour réduire le problème à une variante de l'algorithme d'Euclide. Ils sont un outil fondamental en calcul formel , car les systèmes de calcul formel les utilisent systématiquement pour simplifier les fractions. Inversement, la plupart de la théorie moderne du GCD polynomial a été développée pour satisfaire le besoin d'efficacité des systèmes de calcul formel.

Définition générale

Soient p et q des polynômes à coefficients dans un domaine intégral F , typiquement un corps ou les entiers. Un plus grand diviseur commun de p et q est un polynôme d qui divise p et q , et tel que chaque diviseur commun de p et q divise également d . Chaque paire de polynômes (pas les deux à zéro) a un PGCD si et seulement si F est un domaine de factorisation unique .

Si F est un corps et que p et q ne sont pas tous les deux nuls, un polynôme d est le plus grand diviseur commun si et seulement s'il divise à la fois p et q , et il a le plus grand degré parmi les polynômes ayant cette propriété. Si p = q = 0 , le PGCD est égal à 0. Cependant, certains auteurs considèrent qu'il n'est pas défini dans ce cas.

Le plus grand diviseur commun de p et q est généralement noté " pgcd( p , q ) ".

Le plus grand commun diviseur n'est pas unique : si d est un PGCD de p et q , alors le polynôme f est un autre PGCD si et seulement s'il existe un élément inversible u de F tel que

${\displaystyle f=ud}$

et

${\displaystyle d=u^{-1}f}$.

En d'autres termes, le PGCD est unique à la multiplication près par une constante inversible.

Dans le cas des entiers, cette indétermination a été réglée en choisissant, comme PGCD, l'unique qui est positif (il y en a un autre, qui est son contraire). Avec cette convention, le PGCD de deux entiers est également le plus grand diviseur commun (pour l'ordre habituel). Cependant, comme il n'y a pas d' ordre total naturel pour les polynômes sur un domaine entier, on ne peut pas procéder de la même manière ici. Pour les polynômes univariés sur un corps, on peut en outre exiger que le PGCD soit monique (c'est-à-dire qu'il ait 1 comme coefficient de degré le plus élevé), mais dans les cas plus généraux, il n'y a pas de convention générale. Par conséquent, des égalités comme d = gcd( p , q ) ou gcd( p , q ) = gcd( r , s ) sont des abus de notation courants qui devraient être lus " d est un PGCD de p et q " et " p et q ont le même ensemble de PGCD que r et s ". En particulier, pgcd( p , q ) = 1 signifie que les constantes inversibles sont les seuls diviseurs communs. Dans ce cas, par analogie avec le cas des entiers, on dit que p et q sont polynômes premiers entre eux .

Propriétés

• Comme indiqué plus haut, le PGCD de deux polynômes existe si les coefficients appartiennent soit à un corps, l'anneau des entiers, soit plus généralement à un domaine de factorisation unique .
• Si c est un diviseur commun de p et q , alors c divise leur PGCD.
• ${\displaystyle \gcd(p,q)=\gcd(q,p).}$
• ${\displaystyle \gcd(p,q)=\gcd(q,p+rq)}$pour tout polynôme r . Cette propriété est à la base de la preuve de l'algorithme d'Euclide.
• Pour tout élément inversible k de l'anneau des coefficients, .${\displaystyle \gcd(p,q)=\gcd(p,kq)}$
• Par conséquent, pour tout scalaire tel qu'il est inversible.${\displaystyle \gcd(p,q)=\gcd(a_{1}p+b_{1}q,a_{2}p+b_{2}q)}$${\displaystyle a_{1},b_{1},a_{2},b_{2}}$${\displaystyle a_{1}b_{2}-a_{2}b_{1}}$
• Si , alors .${\displaystyle \gcd(p,r)=1}$${\displaystyle \gcd(p,q)=\gcd(p,qr)}$
• Si , alors .${\style d'affichage \gcd(q,r)=1}$${\style d'affichage \gcd(p,qr)=\gcd(p,q)\,\gcd(p,r)}$
• Pour deux polynômes univariés p et q sur un corps, il existe des polynômes a et b , tels que et divise chaque combinaison linéaire de p et q ( identité de Bézout ).${\displaystyle \gcd(p,q)=ap+bq}$${\style d'affichage \gcd(p,q)}$
• Le plus grand diviseur commun de trois polynômes ou plus peut être défini de la même manière que pour deux polynômes. Il peut être calculé récursivement à partir des PGCD de deux polynômes par les identités :

${\displaystyle \gcd(p,q,r)=\gcd(p,\gcd(q,r)),}$

et

${\displaystyle \gcd(p_{1},p_{2},\dots ,p_{n})=\gcd(p_{1},\gcd(p_{2},\dots ,p_{n})) .}$

GCD à la main calcul

Il existe plusieurs façons de trouver le plus grand diviseur commun de deux polynômes. Deux d'entre eux sont :

1. La factorisation de polynômes , dans laquelle on retrouve les facteurs de chaque expression, sélectionne ensuite l'ensemble des facteurs communs détenus par tous à l'intérieur de chaque ensemble de facteurs. Cette méthode ne peut être utile que dans des cas simples, car la factorisation est généralement plus difficile que le calcul du plus grand diviseur commun.
2. L' algorithme euclidien , qui peut être utilisé pour trouver le PGCD de deux polynômes de la même manière que pour deux nombres.

Affacturage

Pour trouver le PGCD de deux polynômes en utilisant la factorisation, factorisez simplement les deux polynômes complètement. Ensuite, prenez le produit de tous les facteurs communs. À ce stade, nous n'avons pas nécessairement de polynôme monique, alors multipliez-le finalement par une constante pour en faire un polynôme monique. Ce sera le PGCD des deux polynômes car il inclut tous les diviseurs communs et est unitaire.

Exemple un : Trouvez le PGCD de x ² + 7 x + 6 et x ² − 5 x − 6 .

x ² + 7 x + 6 = ( x + 1)( x + 6)

x ² − 5 x − 6 = ( x + 1)( x − 6)

Ainsi, leur PGCD est x + 1 .

Algorithme euclidien

La factorisation des polynômes peut être difficile, surtout si les polynômes ont un degré élevé. L' algorithme d'Euclide est une méthode qui fonctionne pour n'importe quelle paire de polynômes. Il fait un usage répété de la division euclidienne . Lorsque vous utilisez cet algorithme sur deux nombres, la taille des nombres diminue à chaque étape. Avec les polynômes, le degré des polynômes diminue à chaque étape. Le dernier reste non nul, rendu monique si nécessaire, est le PGCD des deux polynômes.

Plus précisément, pour trouver le PGCD de deux polynômes a ( x ) et b ( x ) , on peut supposer b 0 (sinon, le PGCD est a ( x ) ), et

${\displaystyle \deg(b(x))\leq \deg(a(x))\,.}$

La division euclidienne fournit deux polynômes q ( x ) , le quotient et r ( x ) , le reste tel que

${\displaystyle a(x)=q_{0}(x)b(x)+r_{0}(x)\qquad {\text{and}}\qquad \deg(r_{0}(x))< \deg(b(x))}$

Un polynôme g ( x ) divise à la fois a ( x ) et b ( x ) si et seulement s'il divise à la fois b ( x ) et r ₀ ( x ) . Ainsi

${\displaystyle \gcd(a(x),b(x))=\gcd(b(x),r_{0}(x)).}$

Réglage

${\style d'affichage a_{1}(x)=b(x),b_{1}(x)=r_{0}(x),}$

on peut répéter la division euclidienne pour obtenir de nouveaux polynômes q ₁ ( x ), r ₁ ( x ), a ₂ ( x ), b ₂ ( x ) et ainsi de suite. A chaque étape nous avons

${\displaystyle \deg(a_{k+1})+\deg(b_{k+1})<\deg(a_{k})+\deg(b_{k}),}$

donc la séquence finira par atteindre un point auquel

${\style d'affichage b_{N}(x)=0}$

et on a le GCD :

${\displaystyle \gcd(a,b)=\gcd(a_{1},b_{1})=\cdots =\gcd(a_{N},0)=a_{N}.}$

Exemple : trouver le PGCD de x ² + 7 x + 6 et x ² − 5 x − 6 :

x ² + 7 x + 6 = 1 ( x ² − 5 x − 6) + (12 x + 12)

x ² − 5 x − 6 = (12 x + 12) ( 1/12 x −1/2) + 0

Étant donné que 12 x + 12 est le dernier reste non nul, il s'agit d'un PGCD des polynômes d'origine et le PGCD unitaire est x + 1 .

Dans cet exemple, il n'est pas difficile d'éviter d'introduire des dénominateurs en factorisant 12 avant la deuxième étape. Cela peut toujours être fait en utilisant des séquences de pseudo-restes , mais, sans précaution, cela peut introduire de très grands nombres entiers lors du calcul. Par conséquent, pour le calcul informatique, d'autres algorithmes sont utilisés, qui sont décrits ci-dessous.

Cette méthode ne fonctionne que si l'on peut tester l'égalité à zéro des coefficients qui interviennent lors du calcul. Ainsi, en pratique, les coefficients doivent être des entiers , des nombres rationnels , des éléments d'un corps fini , ou doivent appartenir à une extension de corps de type fini de l'un des corps précédents. Si les coefficients sont des nombres à virgule flottante qui représentent des nombres réels qui ne sont connus qu'approximativement, alors il faut connaître le degré du PGCD pour avoir un résultat de calcul bien défini (c'est un résultat numériquement stable ; dans ce cas d'autres techniques peuvent être utilisées , généralement basé sur une décomposition en valeurs singulières .

Polynômes univariés avec des coefficients dans un champ

Le cas des polynômes univariés sur un corps est particulièrement important pour plusieurs raisons. Premièrement, c'est le cas le plus élémentaire et apparaît donc dans la plupart des premiers cours d'algèbre. Deuxièmement, c'est très similaire au cas des entiers, et cette analogie est à l'origine de la notion de domaine euclidien . Une troisième raison est que la théorie et les algorithmes pour le cas multivarié et pour les coefficients dans un domaine de factorisation unique sont fortement basés sur ce cas particulier. Enfin, les algorithmes GCD polynomiaux et les algorithmes dérivés permettent d'obtenir des informations utiles sur les racines d'un polynôme, sans les calculer.

Division euclidienne

La division euclidienne des polynômes, qui est utilisée dans l'algorithme d' Euclide pour le calcul des PGCD, est très similaire à la division euclidienne des nombres entiers. Son existence repose sur le théorème suivant : Étant donnés deux polynômes univariés a et b 0 définis sur un corps, il existe deux polynômes q (le quotient ) et r (le reste ) qui satisfont

${\style d'affichage a=bq+r}$

et

${\displaystyle \deg(r)<\deg(b),}$

où "deg(...)" désigne le degré et le degré du polynôme zéro est défini comme étant négatif. De plus, q et r sont définis de manière unique par ces relations.

La différence avec la division euclidienne des entiers est que, pour les entiers, le degré est remplacé par la valeur absolue, et que pour avoir l'unicité il faut supposer que r est non négatif. Les anneaux pour lesquels un tel théorème existe sont appelés domaines euclidiens .

Comme pour les entiers, la division euclidienne des polynômes peut être calculée par l' algorithme de division longue . Cet algorithme est généralement présenté pour le calcul papier-crayon, mais il fonctionne bien sur les ordinateurs lorsqu'il est formalisé comme suit (notez que les noms des variables correspondent exactement aux régions de la feuille de papier dans un calcul crayon-papier de longue division). Dans le calcul suivant, "deg" représente le degré de son argument (avec la convention deg(0) < 0 ), et "lc" représente le coefficient dominant, le coefficient du plus haut degré de la variable.

Division euclidienne

Entrée :  a et b ≠ 0 deux polynômes dans la variable x ;
Sortie :  q , le quotient, et r , le reste ;

Begin
     q  := 0
     r  := a 
    d  := deg( b )
     c  := lc( b )
     while deg( r ) ≥ d  do
         s  :=lc( r )/c x deg( r )− d
         q  := q + s 
        r  := r − sb 
    end do 
    return ( q , r )
 end

La preuve de la validité de cet algorithme repose sur le fait que durant toute la boucle « while », on a a = bq + r et deg( r ) est un entier non négatif qui décroît à chaque itération. Ainsi, la preuve de la validité de cet algorithme prouve également la validité de la division euclidienne.

L'algorithme d'Euclide

Comme pour les entiers, la division euclidienne permet de définir l'algorithme d' Euclide pour le calcul des PGCD.

A partir de deux polynômes a et b , l'algorithme d'Euclide consiste à remplacer récursivement le couple ( a , b ) par ( b , rem( a , b )) (où " rem( a , b ) " désigne le reste de la division euclidienne, calculé par l'algorithme de la section précédente), jusqu'à b = 0. Le PGCD est le dernier reste non nul.

L'algorithme d'Euclide peut être formalisé dans le style de programmation récursive comme :

${\displaystyle \gcd(a,b):={\text{if }}b=0{\text{ then }}a{\text{ else }}\gcd(b,\operatorname {rem} (a, b)).}$

Dans le style de programmation impératif, le même algorithme devient, donnant un nom à chaque reste intermédiaire :

${\displaystyle {\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}}$

pour (;;) faire${\style d'affichage i:=1}$${\displaystyle r_{i}\neq 0}$${\style d'affichage i:=i+1}$
     do final${\displaystyle {\begin{aligned}r_{i+1}&:=\operatorname {rem} (r_{i-1},r_{i})\end{aligned}}}$


revenir ${\style d'affichage (r_{i-1}).}$

La suite des degrés des r _i est strictement décroissante. Ainsi , après, au plus deg ( b ) étapes, obtenir un jeu reste nul, disons r _k . Comme ( a , b ) et ( b , rem( a , b )) ont les mêmes diviseurs, l'ensemble des diviseurs communs n'est pas modifié par l'algorithme d'Euclide et donc toutes les paires ( r _i , r _{i +1} ) ont le même ensemble de diviseurs communs. Les diviseurs communs de a et b sont donc les diviseurs communs de r _{k -1} et 0. Ainsi r _{k -1} est un PGCD de a et b . Cela prouve non seulement que l'algorithme d'Euclide calcule les GCD, mais prouve également que les GCD existent.

Identité de Bézout et algorithme GCD étendu

L'identité de Bézout est un théorème lié à GCD, initialement prouvé pour les entiers, qui est valable pour tout domaine idéal principal . Dans le cas des polynômes univariés sur un corps, cela peut s'énoncer comme suit.

Si g est le plus grand commun diviseur de deux polynômes a et b (pas tous les deux nuls), alors il y a deux polynômes u et v tels que

${\displaystyle au+bv=g\quad }$ (Identité de Bézout)

et soit u = 1, v = 0 , soit u = 0, v = 1 , ou

${\displaystyle \deg(u)<\deg(b)-\deg(g),\quad \deg(v)<\deg(a)-\deg(g).}$

L'intérêt de ce résultat dans le cas des polynômes est qu'il existe un algorithme efficace pour calculer les polynômes u et v , Cet algorithme diffère de l'algorithme d'Euclide par quelques calculs supplémentaires effectués à chaque itération de la boucle. On l'appelle donc algorithme GCD étendu . Une autre différence avec l'algorithme d'Euclide est qu'il utilise également le quotient, noté « quo », de la division euclidienne au lieu du reste uniquement. Cet algorithme fonctionne comme suit.

Algorithme GCD étendu

Entrée :  a , b , polynômes univariés

Sortie :
     g , le PGCD de a et b 
    u , v , comme dans l'instruction ci-dessus
     a 1 , b 1 , tel que
         Begin${\displaystyle {\begin{aligned}a=ga_{1}\\b=gb_{1}\end{aligned}}}$

    ${\displaystyle {\begin{array}{ll}r_{0}=a&r_{1}=b\\s_{0}=1&s_{1}=0\\t_{0}=0&t_{1}=1\ fin{tableau}}}$
  
    pour ( i = 1 ; r i ≠ 0 ; i = i + 1 ) ne 
        bout pas fin${\displaystyle q=\operatorname {quo} (r_{i-1},r_{i})}$
        ${\displaystyle {\begin{aligned}r_{i+1}&=r_{i-1}-qr_{i}\\s_{i+1}&=s_{i-1}-qs_{i}\ \t_{i+1}&=t_{i-1}-qt_{i}\end{aligned}}}$
    
    ${\displaystyle {\begin{aligned}g&=r_{i-1}\\u&=s_{i-1}\\v&=t_{i-1}\end{aligned}}}$
    ${\displaystyle {\begin{aligned}a_{1}&=(-1)^{i-1}t_{i}\\b_{1}&=(-1)^{i}s_{i}\ fin{aligné}}}$

La preuve que l'algorithme satisfait sa spécification de sortie repose sur le fait que, pour tout i, nous avons

${\displaystyle r_{i}=as_{i}+bt_{i}}$

${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=s_{i}t_{i-1}-t_{i}s_{i-1},}$

cette dernière égalité impliquant

${\displaystyle s_{i}t_{i+1}-t_{i}s_{i+1}=(-1)^{i}.}$

L'assertion sur les degrés découle du fait qu'à chaque itération, les degrés de s _i et t _i augmentent au plus lorsque le degré de r _i diminue.

Une caractéristique intéressante de cet algorithme est que, lorsque les coefficients de l'identité de Bezout sont nécessaires, on obtient gratuitement le quotient des polynômes d'entrée par leur PGCD.

Arithmétique des extensions algébriques

Une application importante de l'algorithme GCD étendu est qu'il permet de calculer la division en extensions de champ algébrique .

Soit L une extension algébrique d'un corps K , engendrée par un élément dont le polynôme minimal f est de degré n . Les éléments de L sont généralement représentés par des polynômes univariés sur K de degré inférieur à n .

L'addition dans L est simplement l'addition de polynômes :

${\displaystyle a+_{L}b=a+_{K[X]}b.}$

La multiplication dans L est la multiplication des polynômes suivie de la division par f :

${\displaystyle a\cdot _{L}b=\operatorname {rem} (a._{K[X]}b,f).}$

L'inverse d'un élément non nul a de L est le coefficient u dans l'identité de Bézout au + fv = 1 , qui peut être calculé par l'algorithme GCD étendu. (le PGCD est 1 car le polynôme minimal f est irréductible). L'inégalité des degrés dans la spécification de l'algorithme GCD étendu montre qu'une division supplémentaire par f n'est pas nécessaire pour obtenir deg( u ) < deg( f ).

Sous-résultats

Dans le cas des polynômes univariés, il existe une forte relation entre les plus grands diviseurs communs et les résultantes . Plus précisément, la résultante de deux polynômes P , Q est une fonction polynomiale des coefficients de P et Q qui vaut zéro si et seulement si le PGCD de P et Q n'est pas constant.

La théorie des sous-résultantes est une généralisation de cette propriété qui permet de caractériser génériquement le PGCD de deux polynômes, et la résultante est le 0-ième polynôme sous-résultant.

Le i -ème polynôme sous- résultant S _i ( P , Q ) de deux polynômes P et Q est un polynôme de degré au plus i dont les coefficients sont des fonctions polynomiales des coefficients de P et Q , et le i -ème coefficient sous-résultant principal s _i ( P , Q ) est le coefficient de degré i de S _i ( P , Q ). Ils ont la propriété que le PGCD de P et Q a un degré d si et seulement si

${\displaystyle s_{0}(P,Q)=\cdots =s_{d-1}(P,Q)=0\ ,s_{d}(P,Q)\neq 0}$.

Dans ce cas, S _d ( P , Q ) est un PGCD de P et Q et

${\displaystyle S_{0}(P,Q)=\cdots =S_{d-1}(P,Q)=0.}$

Chaque coefficient des polynômes sous-résultants est défini comme le déterminant d'une sous-matrice de la matrice de Sylvester de P et Q . Cela implique que les sous-résultants se "spécialisent" bien. Plus précisément, les sous-résultants sont définis pour les polynômes sur tout anneau commutatif R , et ont la propriété suivante.

Soit φ un homomorphisme d'anneaux de R dans un autre anneau commutatif S . Il s'étend à un autre homomorphisme, noté aussi φ entre les polynômes anneaux sur R et S . Alors, si P et Q sont des polynômes univariés à coefficients dans R tels que

${\displaystyle \deg(P)=\deg(\varphi (P))}$

et

${\displaystyle \deg(Q)=\deg(\varphi (Q)),}$

puis les polynômes subresultant et les principaux coefficients de subresultant de φ ( P ) et φ ( Q ) sont l'image par φ de ceux des P et Q .

Les sous-résultantes ont deux propriétés importantes qui les rendent fondamentales pour le calcul sur ordinateur du PGCD de deux polynômes à coefficients entiers. Premièrement, leur définition par des déterminants permet de borner, par l' inégalité d'Hadamard , la taille des coefficients du PGCD. Deuxièmement, cette borne et la propriété d'une bonne spécialisation permettent de calculer le PGCD de deux polynômes à coefficients entiers par calcul modulaire et théorème des restes chinois (voir ci - dessous ).

Définition technique

Laisser

${\displaystyle P=p_{0}+p_{1}X+\cdots +p_{m}X^{m},\quad Q=q_{0}+q_{1}X+\cdots +q_{n}X ^{n}.}$

être deux polynômes univariés à coefficients dans un corps K . Désignons par l' espace vectoriel K de dimension i des polynômes de degré inférieur à i . Pour nombre entier non négatif i tel que i ≤ m et i ≤ n , laisse ${\displaystyle {\mathcal {P}}_{i}}$

${\displaystyle \varphi _{i}:{\mathcal {P}}_{ni}\times {\mathcal {P}}_{mi}\rightarrow {\mathcal {P}}_{m+ni}}$

être l'application linéaire telle que

${\displaystyle \varphi _{i}(A,B)=AP+BQ.}$

La résultante de P et Q est le déterminant de la matrice de Sylvester , qui est la matrice (carrée) de sur les bases des puissances de X . De même, le polynôme i -sous-résultant est défini en terme de déterminants de sous-matrices de la matrice de${\displaystyle \varphi _{0}}$${\displaystyle \varphi _{i}.}$

Décrivons plus précisément ces matrices ;

Soit p _i = 0 pour i < 0 ou i > m , et q _i = 0 pour i < 0 ou i > n . La matrice de Sylvester est la ( m + n ) × ( m + n )-matrice telle que le coefficient de la i -ième ligne et de la j -ième colonne est p _{m + j − i} pour j ≤ n et q _{j − i} pour j > n :

${\displaystyle S={\begin{pmatrix}p_{m}&0&\cdots &0&q_{n}&0&\cdots &0\\p_{m-1}&p_{m}&\cdots &0&q_{n-1}&q_{n }&\cdots &0\\p_{m-2}&p_{m-1}&\ddots &0&q_{n-2}&q_{n-1}&\ddots &0\\\vdots &\vdots &\ddots &p_{ m}&\vdots &\vdots &\ddots &q_{n}\\\vdots &\vdots &\cdots &p_{m-1}&\vdots &\vdots &\cdots &q_{n-1}\\p_{ 0}&p_{1}&\cdots &\vdots &q_{0}&q_{1}&\cdots &\vdots \\0&p_{0}&\ddots &\vdots &0&q_{0}&\ddots &\vdots &\ \\vdots &\vdots &\ddots &p_{1}&\vdots &\vdots &\ddots &q_{1}\\0&0&\cdots &p_{0}&0&0&\cdots &q_{0}\end{pmatrix}}.}$

La matrice T _i de est la ( m + n − i ) × ( m + n − 2 i )-sous-matrice de S qui est obtenue en supprimant les i dernières lignes de zéros dans la sous-matrice des colonnes 1 à n − i et n + 1 à m + n − i de S (c'est-à-dire en supprimant les i colonnes de chaque bloc et les i dernières rangées de zéros). Le coefficient sous-résultant principal s _i est le déterminant des m + n − 2 i premières lignes de T _i . ${\displaystyle \varphi _{i}}$

Soit V _i la matrice ( m + n − 2 i ) × ( m + n − i ) définie comme suit. Nous ajoutons d'abord ( i + 1) colonnes de zéros à droite de la ( m + n − 2 i − 1) × ( m + n − 2 i − 1) matrice identité . Ensuite, nous bordons le bas de la matrice résultante par une ligne constituée de ( m + n − i − 1) zéros suivis de X ⁱ , X ^{i −1} , ..., X , 1 :

${\displaystyle V_{i}={\begin{pmatrix}1&0&\cdots &0&0&0&\cdots &0\\0&1&\cdots &0&0&0&\cdots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\ddots & \vdots &0\\0&0&\cdots &1&0&0&\cdots &0\\0&0&\cdots &0&X^{i}&X^{i-1}&\cdots &1\end{pmatrix}}.}$

Avec cette notation, le i -ième polynôme subresultant est le déterminant de la matrice de produit V _i T _i . Son coefficient de degré j est le déterminant de la sous-matrice carrée de T _i constituée de ses m + n − 2 i − 1 premières lignes et de la ( m + n − i − j )-ème ligne.

Esquisse de la preuve

Il n'est pas évident que, telles que définies, les sous-résultants aient les propriétés souhaitées. Néanmoins, la démonstration est assez simple si l'on met ensemble les propriétés de l'algèbre linéaire et celles des polynômes.

Telles que définies, les colonnes de la matrice T _i sont les vecteurs des coefficients de certains polynômes appartenant à l'image de . La définition du i- ième polynôme sous- résultant S _i montre que le vecteur de ses coefficients est une combinaison linéaire de ces vecteurs colonnes, et donc que S _i appartient à l'image de${\displaystyle \varphi _{i}}$${\displaystyle \varphi _{i}.}$

Si le degré du PGCD est supérieur à i , alors l'identité de Bézout montre que tout polynôme non nul dans l'image de a un degré supérieur à i . Ceci implique que S _i =0. ${\displaystyle \varphi _{i}}$

Si par contre le degré du PGCD est i , alors l'identité de Bézout permet à nouveau de prouver que les multiples du PGCD qui ont un degré inférieur à m + n − i sont à l'image de . L'espace vectoriel de ces multiples a la dimension m + n − 2 i et a une base de polynômes de degrés différents deux à deux, pas plus petits que i . Ceci implique que la sous-matrice des m + n − 2 i premières lignes de la forme échelon colonne de T _i est la matrice identité et donc que s _i n'est pas 0. Ainsi S _i est un polynôme à l'image de , qui est un multiple du PGCD et a le même degré. C'est donc le plus grand commun diviseur. ${\displaystyle \varphi _{i}}$${\displaystyle \varphi _{i}}$

GCD et recherche de racine

Factorisation sans carré

La plupart des algorithmes de recherche de racines se comportent mal avec des polynômes qui ont plusieurs racines . Il est donc utile de les détecter et de les supprimer avant d'appeler un algorithme de recherche de racine. Un calcul PGCD permet de détecter l'existence de racines multiples, puisque les racines multiples d'un polynôme sont les racines du PGCD du polynôme et de sa dérivée .

Après avoir calculé le PGCD du polynôme et sa dérivée, d'autres calculs de PGCD fournissent la factorisation complète sans carré du polynôme, qui est une factorisation

${\displaystyle f=\prod _{i=1}^{\deg(f)}f_{i}^{i}}$

où, pour chaque i , le polynôme f _i est soit 1 si f n'a pas de racine de multiplicité i ou est un polynôme sans carré (c'est-à-dire un polynôme sans racine multiple) dont les racines sont exactement les racines de multiplicité i de f (voir l'algorithme de Yun ).

Ainsi, la factorisation sans carré réduit la recherche de racine d'un polynôme à racines multiples à la recherche de racine de plusieurs polynômes sans carré de degré inférieur. La factorisation sans carré est également la première étape de la plupart des algorithmes de factorisation polynomiale .

Séquence de Sturm

La suite de Sturm d'un polynôme à coefficients réels est la suite des restes fournie par une variante de l'algorithme d'Euclide appliquée au polynôme et à sa dérivée. Pour obtenir la séquence de Sturm, on remplace simplement l'instruction

${\displaystyle r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})}$

de l'algorithme d'Euclide par

${\displaystyle r_{i+1}:=-\operatorname {rem} (r_{i-1},r_{i}).}$

Soit V ( a ) le nombre de changements de signes dans la séquence, lorsqu'il est évalué en un point a . Le théorème de Sturm affirme que V ( a ) − V ( b ) est le nombre de racines réelles du polynôme dans l'intervalle [ a , b ]. Ainsi la séquence de Sturm permet de calculer le nombre de racines réelles dans un intervalle donné. En subdivisant l'intervalle jusqu'à ce que chaque sous-intervalle contienne au plus une racine, cela fournit un algorithme qui localise les racines réelles dans des intervalles de petite longueur arbitraire.

PGCD sur un anneau et son corps de fractions

Dans cette section, nous considérons des polynômes sur un domaine de factorisation unique R , typiquement l'anneau des entiers, et sur son corps de fractions F , typiquement le domaine des nombres rationnels, et nous notons R [ X ] et F [ X ] le anneaux de polynômes dans un ensemble de variables sur ces anneaux.

Factorisation primitive partie-contenu

Le contenu d'un polynôme p ∈ R [ X ], noté "cont ( p )", est le PGCD de ses coefficients. Un polynôme q ∈ F [ X ] peut s'écrire

${\displaystyle q={\frac {p}{c}}}$

où p ∈ R [ X ] et c ∈ R : il suffit de prendre pour c un multiple de tous les dénominateurs des coefficients de q (par exemple leur produit) et p = cq . Le contenu de q est défini comme :

${\displaystyle \operatorname {cont} (q)={\frac {\operatorname {cont} (p)}{c}}.}$

Dans les deux cas, le contenu est défini à la multiplication par une unité de R .

La partie primitive d'un polynôme dans R [ X ] ou F [ X ] est définie par

${\displaystyle \operatorname {primpart} (p)={\frac {p}{\operatorname {cont} (p)}}.}$

Dans les deux cas, c'est un polynôme dans R [ X ] qui est primitif , ce qui signifie que 1 est un PGCD de ses coefficients.

Ainsi, chaque polynôme dans R [ X ] ou F [ X ] peut être factorisé comme

${\displaystyle p=\operatorname {cont} (p)\,\operatorname {primpart} (p),}$

et cette factorisation est unique jusqu'à la multiplication du contenu par une unité de R et de la partie primitive par l'inverse de cette unité.

Le lemme de Gauss implique que le produit de deux polynômes primitifs est primitif. Il s'ensuit que

${\displaystyle \operatorname {primpart} (pq)=\operatorname {primpart} (p)\operatorname {primpart} (q)}$

et

${\displaystyle \operatorname {cont} (pq)=\operatorname {cont} (p)\operatorname {cont} (q).}$

Relation entre le PGCD sur R et sur F

Les relations de la section précédente impliquent une relation forte entre les PGCD dans R [ X ] et dans F [ X ]. Pour éviter les ambiguïtés, la notation " gcd " sera indexée, dans la suite, par l'anneau dans lequel le PGCD est calculé.

Si q ₁ et q ₂ appartiennent à F [ X ], alors

${\displaystyle \operatorname {primpart} (\gcd _{F[X]}(q_{1},q_{2}))=\gcd _{R[X]}(\operatorname {primpart} (q_{1 }),\operatorname {primpart} (q_{2})).}$

Si p ₁ et p ₂ appartiennent à R [ X ], alors

${\displaystyle \gcd _{R[X]}(p_{1},p_{2})=\gcd _{R}(\operatorname {cont} (p_{1}),\operatorname {cont} (p_ {2}))\gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2})),}$

et

${\displaystyle \gcd _{R[X]}(\operatorname {primpart} (p_{1}),\operatorname {primpart} (p_{2}))=\operatorname {primpart} (\gcd _{F[ X]}(p_{1},p_{2})).}$

Ainsi, le calcul des PGCD polynomiaux est essentiellement le même problème sur F [ X ] et sur R [ X ].

Pour les polynômes univariés sur les nombres rationnels, on peut penser que l'algorithme d'Euclide est une méthode pratique pour calculer le PGCD. Cependant, il s'agit de simplifier un grand nombre de fractions d'entiers, et l'algorithme qui en résulte n'est pas efficace. Pour cette raison, des méthodes ont été conçues pour modifier l'algorithme d'Euclide pour ne travailler qu'avec des polynômes sur les entiers. Ils consistent à remplacer la division euclidienne, qui introduit des fractions, par une pseudo-division , et à remplacer la séquence reste de l'algorithme d'Euclide par des séquences dites pseudo-reste (voir ci - dessous ).

Preuve que GCD existe pour les polynômes multivariés

Dans la section précédente, nous avons vu que le PGCD des polynômes dans R [ X ] peut être déduit des PGCD dans R et dans F [ X ]. Un examen plus approfondi de la preuve montre que cela permet de prouver l'existence de PGCD dans R [ X ], s'ils existent dans R et dans F [ X ]. En particulier, si des PGCD existent dans R , et si X se réduit à une variable, cela prouve que des PGCD existent dans R [ X ] (l'algorithme d'Euclid prouve l'existence de PGCD dans F [ X ]).

Un polynôme en n variables peut être considéré comme un polynôme univarié sur l'anneau des polynômes en ( n − 1) variables. Ainsi, une récursivité sur le nombre de variables montre que si les PGCD existent et peuvent être calculés dans R , alors ils existent et peuvent être calculés dans chaque anneau polynomial multivarié sur R . En particulier, si R est soit l'anneau des entiers soit un corps, alors les PGCD existent dans R [ x ₁ ,..., x _n ], et ce qui précède fournit un algorithme pour les calculer.

La preuve qu'un anneau polynomial sur un domaine de factorisation unique est également un domaine de factorisation unique est similaire, mais elle ne fournit pas d'algorithme, car il n'existe pas d'algorithme général pour factoriser des polynômes univariés sur un champ (il existe des exemples de champs pour lesquels il existe n'existe pas d'algorithme de factorisation pour les polynômes univariés).

Séquences pseudo-restes

Dans cette section, nous considérons un domaine intégral Z (typiquement l'anneau Z des entiers) et son corps de fractions Q (typiquement le corps Q des nombres rationnels). Étant donné deux polynômes A et B dans l'anneau polynomial univarié Z [ X ], la division euclidienne (sur Q ) de A par B fournit un quotient et un reste qui peuvent ne pas appartenir à Z [ X ].

Car, si l'on applique l'algorithme d'Euclide aux polynômes suivants

${\displaystyle X^{8}+X^{6}-3X^{4}-3X^{3}+8X^{2}+2X-5}$

et

${\style d'affichage 3X^{6}+5X^{4}-4X^{2}-9X+21,}$

les restes successifs de l'algorithme d'Euclide sont

${\displaystyle {\begin{aligned}&-{\tfrac {5}{9}}X^{4}+{\tfrac {1}{9}}X^{2}-{\tfrac {1}{ 3}},\\&-{\tfrac {117}{25}}X^{2}-9X+{\tfrac {441}{25}},\\&{\tfrac {233150}{19773}}X -{\tfrac {102500}{6591}},\\&-{\tfrac {1288744821}{543589225}}.\end{aligned}}}$

On voit que, malgré le petit degré et la petite taille des coefficients des polynômes d'entrée, il faut manipuler et simplifier des fractions entières de taille assez grande.

La pseudo-division a été introduite pour permettre une variante de l'algorithme d'Euclide pour laquelle tous les restes appartiennent à Z [ X ].

Si et et un ≥ b , la pseudo-reste de la pseudo-division de A par B , notée prem ( A , B ) est ${\style d'affichage \deg(A)=a}$${\style d'affichage \deg(B)=b}$

${\displaystyle \operatorname {prem} (A,B)=\operatorname {rem} (\operatorname {lc} (B)^{a-b+1}A,B),}$

où lc( B ) est le coefficient dominant de B (le coefficient de X ^b ).

Le pseudo-reste de la pseudo-division de deux polynômes dans Z [ X ] appartient toujours à Z [ X ].

Une séquence pseudo-reste est la séquence des (pseudo) restes r _i obtenus en remplaçant l'instruction

${\displaystyle r_{i+1}:=\operatorname {rem} (r_{i-1},r_{i})}$

de l'algorithme d'Euclide par

${\displaystyle r_{i+1} :={\frac {\operatorname {prem} (r_{i-1},r_{i})}{\alpha }},}$

où α est un élément de Z qui divise exactement chaque coefficient du numérateur. Différents choix de α donnent différentes séquences pseudo-restantes, qui sont décrites dans les sous - sections suivantes.

Comme les diviseurs communs de deux polynômes ne sont pas modifiés si les polynômes sont multipliés par des constantes inversibles (dans Q ), le dernier terme non nul dans une séquence pseudo-reste est un PGCD (dans Q [ X ]) des polynômes d'entrée. Par conséquent, les séquences pseudo-restes permettent de calculer les PGCD dans Q [ X ] sans introduire de fractions dans Q .

Dans certains contextes, il est essentiel de contrôler le signe du coefficient dominant du pseudo-reste. Cela est généralement le cas lors du calcul des résultantes et subresultants , ou pour utiliser le théorème de Sturm . Ce contrôle peut se faire soit en remplaçant lc( B ) par sa valeur absolue dans la définition du pseudo-reste, soit en contrôlant le signe de α (si α divise tous les coefficients d'un reste, il en est de même pour – α ) .

Séquence pseudo-reste triviale

La suite des restes la plus simple (à définir) consiste à prendre toujours α = 1 . En pratique, ce n'est pas intéressant, car la taille des coefficients croît de façon exponentielle avec le degré des polynômes d'entrée. Ceci apparaît clairement sur l'exemple de la section précédente, pour laquelle les pseudo-restes successifs sont

${\style d'affichage -15\,X^{4}+3\,X^{2}-9,}$

${\displaystyle 15795\,X^{2}+30375\,X-59535,}$

${\style d'affichage 1254542875143750\,X-1654608338437500,}$

${\style d'affichage 12593338795500743100931141992187500.}$

Le nombre de chiffres des coefficients des restes successifs est plus que doublé à chaque itération de l'algorithme. C'est un comportement typique des séquences de pseudo-restes triviales.

Séquence primitive pseudo-reste

La séquence pseudo-reste primitive consiste à prendre pour α le contenu du numérateur. Ainsi tous les r _i sont des polynômes primitifs.

La séquence pseudo-reste primitive est la séquence pseudo-reste, qui génère les plus petits coefficients. Cependant, il nécessite de calculer un nombre de PGCD dans Z , et n'est donc pas suffisamment efficace pour être utilisé en pratique, surtout lorsque Z est lui-même un anneau polynomial.

Avec la même entrée que dans les sections précédentes, les restes successifs, après division par leur contenu sont

${\style d'affichage -5\,X^{4}+X^{2}-3,}$

${\style d'affichage 13\,X^{2}+25\,X-49,}$

${\style d'affichage 4663\,X-6150,}$

${\style d'affichage 1.}$

La petite taille des coefficients masque le fait qu'un certain nombre d'entiers PGCD et divisions par PGCD ont été calculés.

Séquence pseudo-reste sous-résultante

Une séquence sous-résultante peut également être calculée avec des pseudo-restes. Le procédé consiste à choisir α de telle sorte que chaque R _i est un polynôme subresultant. Étonnamment, le calcul de α est très facile (voir ci - dessous). Par contre, la preuve de correction de l'algorithme est difficile, car il doit prendre en compte toutes les possibilités de différence de degrés de deux restes consécutifs.

Les coefficients de la séquence sous-résultante sont rarement beaucoup plus grands que ceux de la séquence primitive pseudo-reste. Comme les calculs GCD dans Z ne sont pas nécessaires, la séquence sous-résultante avec des pseudo-restes donne le calcul le plus efficace.

Avec la même entrée que dans les sections précédentes, les restes successifs sont

${\style d'affichage 15\,X^{4}-3\,X^{2}+9,}$

${\style d'affichage 65\,X^{2}+125\,X-245,}$

${\style d'affichage 9326\,X-12300,}$

${\style d'affichage 260708.}$

Les coefficients ont une taille raisonnable. Ils sont obtenus sans aucun calcul GCD, seulement des divisions exactes. Cela rend cet algorithme plus efficace que celui des séquences primitives de pseudo-restes.

L'algorithme calculant la séquence sous-résultante avec des pseudo-restes est donné ci-dessous. Dans cet algorithme, l'entrée ( a , b ) est une paire de polynômes dans Z [X]. Les r _i sont les pseudo-restes successifs dans Z [X], les variables i et d _i sont des entiers non négatifs, et les lettres grecques désignent des éléments dans Z . Les fonctions deg()et rem()désignent le degré d'un polynôme et le reste de la division euclidienne. Dans l'algorithme, ce reste est toujours dans Z [X]. Enfin les divisions notées / sont toujours exactes et ont leur résultat soit dans Z [X] soit dans Z .

${\displaystyle {\begin{aligned}r_{0}:=a\\r_{1}:=b\end{aligned}}}$
for (;;) do${\style d'affichage i:=1}$${\displaystyle r_{i}\neq 0}$${\style d'affichage i:=i+1;}$
     if then elseend if end do.${\displaystyle {\begin{aligned}d_{i}&:=\deg(r_{i-1})-\deg(r_{i})\\\gamma _{i}&:=\operatorname {lc } (r_{i})\end{aligned}}}$
     ${\style d'affichage i=1}$ 
        ${\displaystyle {\begin{aligned}\beta _{1}&:=(-1)^{d_{1}+1}\\\psi _{1}&:=-1\end{aligned}} }$
    
        ${\displaystyle {\begin{aligned}\beta _{i}&:=-\gamma _{i-1}\psi _{i}^{d_{i}}\\\psi _{i}& : ={\frac {(-\gamma _{i-1})^{d_{i-1}}}{\psi _{i-1}^{d_{i-1}-1}}}\end {aligné}}}$
    
    ${\displaystyle r_{i+1} :={\frac {\operatorname {rem} (\gamma _{i}^{d_{i}+1}r_{i-1},r_{i})}{ \beta _{i}}}}$

Remarque : "lc" représente le coefficient dominant, le coefficient du plus haut degré de la variable.

Cet algorithme calcule non seulement le plus grand diviseur commun (le dernier r _i non nul ), mais aussi tous les polynômes sous-résultants : Le reste r _i est le (deg( r _{i −1} ) − 1) -ième polynôme sous-résultant. Si deg( r _i ) < deg( r _{i −1} ) − 1 , le deg( r _i ) -ième polynôme sous-résultant est lc( r _i ) ^{deg( r _{i −1} )−deg( r _i )−1} r _i . Tous les autres polynômes sous-résultants sont nuls.

Séquence de Sturm avec pseudo-restes

On peut utiliser des pseudo-restes pour construire des séquences ayant les mêmes propriétés que les séquences de Sturm . Cela nécessite de contrôler les signes des pseudo-restes successifs, afin d'avoir les mêmes signes que dans la séquence de Sturm. Cela peut être fait en définissant un pseudo-reste modifié comme suit.

Si et et un ≥ b , la pseudo-prem2 reste modifié ( A , B ) de la pseudo-division de A par B est ${\style d'affichage \deg(A)=a}$${\style d'affichage \deg(B)=b}$

${\displaystyle \operatorname {prem2} (A,B)=-\operatorname {rem} (|\operatorname {lc} (B)|^{a-b+1}A,B),}$

où |lc( B )| est la valeur absolue du coefficient dominant de B (le coefficient de X ^b ).

Pour les polynômes d'entrée avec des coefficients entiers, cela permet de récupérer des séquences de Sturm constituées de polynômes avec des coefficients entiers. La séquence pseudo-reste sous-résultante peut être modifiée de la même manière, auquel cas les signes des restes coïncident avec ceux calculés sur les rationnels.

Notez que l'algorithme de calcul de la pseudo-suite sous-résultante donnée ci-dessus calculera de mauvais polynômes sous-résultants si on utilise à la place de . ${\displaystyle -\mathrm {prem2} (A,B)}$${\displaystyle \operatorname {prem} (A,B)}$

Algorithme GCD modulaire

Si f et g sont des polynômes dans F [ x ] pour un corps de type fini F , l'algorithme d'Euclide est le moyen le plus naturel de calculer leur PGCD. Cependant, les systèmes de calcul formel modernes ne l'utilisent que si F est fini en raison d'un phénomène appelé gonflement d'expression intermédiaire . Bien que les degrés continuent de diminuer au cours de l'algorithme euclidien, si F n'est pas fini, la taille en bits des polynômes peut augmenter (parfois considérablement) pendant les calculs, car les opérations arithmétiques répétées dans F ont tendance à conduire à des expressions plus grandes. Par exemple, l'addition de deux nombres rationnels dont les dénominateurs sont bornés par b conduit à un nombre rationnel dont le dénominateur est borné par b ² , donc dans le pire des cas, la taille en bits pourrait presque doubler en une seule opération.

Pour accélérer le calcul, prenons un anneau D pour lequel f et g sont dans D [ x ], et prenons un idéal I tel que D / I est un anneau fini. Calculez ensuite le PGCD sur cet anneau fini avec l'algorithme d'Euclide. En utilisant des techniques de reconstruction ( théorème des restes chinois , reconstruction rationnelle , etc . ) on peut récupérer le PGCD de f et g à partir de son image modulo un certain nombre d' idéaux I . On peut prouver que cela fonctionne à condition d'écarter les images modulaires avec des degrés non minimaux, et d'éviter les idéaux I modulo dont un coefficient directeur s'annule.

Supposons , , et . Si on prend alors est un anneau fini (pas un corps puisque n'est pas maximal dans ). L'algorithme euclidien appliqué aux images de in réussit et renvoie 1. Cela implique que le PGCD de in doit également être égal à 1. Notez que cet exemple pourrait facilement être traité par n'importe quelle méthode car les degrés étaient trop petits pour que l'expression augmente, mais il illustre que si deux polynômes ont PGCD 1, alors l'algorithme modulaire est susceptible de se terminer après un seul idéal . ${\displaystyle F=\mathbb {Q} ({\sqrt {3}})}$${\displaystyle D=\mathbb {Z} [{\sqrt {3}}]}$${\displaystyle f={\sqrt {3}}x^{3}-5x^{2}+4x+9}$${\displaystyle g=x^{4}+4x^{2}+3{\sqrt {3}}x-6}$${\style d'affichage I=(2)}$${\displaystyle D/I}$${\style d'affichage I}$${\style d'affichage D}$${\style d'affichage f,g}$${\style d'affichage (D/I)[x]}$${\style d'affichage f,g}$${\style d'affichage F[x]}$${\style d'affichage I}$

Voir également

• Liste des sujets polynomiaux
• Algorithme de division multivariée

Les références

• Basu, Saugata ; Pollack, Richard; Roy, Marie-Françoise (2006). Algorithmes en géométrie algébrique réelle, chapitre 4.2 . Springer-Verlag .
• Davenport, James H. ; Siret, Yvon ; Tournier, Évelyne (1988). Calcul algébrique : systèmes et algorithmes pour le calcul algébrique . Traduit du français par A. Davenport et JH Davenport. Presse académique. ISBN 978-0-12-204230-0.
• van Hoeij, M.; Monagan, MB (2004). Algorithmes pour le calcul de GCD polynomial sur des champs de fonctions algébriques . ISSAC 2004. p. 297-304.
• Javadi, SMM ; Monagan, MB (2007). Un algorithme GCD modulaire clairsemé pour les polynômes sur les champs de fonctions algébriques . ISSAC 2007. p. 187-194.
• Knuth, Donald E. (1969). L'art de la programmation informatique II . Addison-Wesley. p. 370-371.
• Knuth, Donald E. (1997). Algorithmes semi-numériques . L'art de la programmation informatique. 2 (troisième éd.). Reading, Massachusetts : Addison-Wesley. p. 439-461, 678-691. ISBN 0-201-89684-2.
• Loos, Rudiger (1982), "Séquences de restes polynomiaux généralisés", dans B. Buchberger; R. Loos ; G. Collins (dir.), Computer Algèbre , Springer Verlag