COURS 10

Pgcd, résultant, et approximants de Padé

Résumé
L’algorithme d’Euclide classique permet de calculer le pgcd et le pgcd
étendu. Il est relié aux résultants qui permettent un calcul d’élimination.
Les calculs efficaces de ces objets seront détaillés dans un cours ultérieur.
Ils sont quasi-optimaux dans le cas univarié.

Les calculs de pgcd sont cruciaux pour la simplification des fractions, qu’il
s’agisse de fractions d’entiers ou de fractions de polynômes. Les algorithmes efficaces
de factorisation de polynômes reposent par ailleurs de manière essentielle sur le pgcd
de polynômes. Comme pour la multiplication, les algorithmes efficaces de pgcd
sont plus complexes dans le cas des entiers que dans le cas des polynômes à cause
des retenues et nous ne détaillons que la version polynomiale. Dans les définitions
et résultats de nature moins algorithmique, nous utilisons le cadre algébrique des
anneaux euclidiens qui permet de traiter simultanément toutes les applications que
nous avons en vue.
L’algorithme d’Euclide pour le calcul du pgcd est présenté en section 1. Dans le
cas de polynômes de K[X], sa complexité est quadratique en nombre d’opérations
dans le corps K. Le résultant est également lié à l’algorithme d’Euclide, ses pro-
priétés et son calcul sont présentés en section 2. En outre, une technique dite
« des sous-résultants » permet de réduire l’explosion de la taille des coefficients in-
termédiaires dont souffre l’algorithme d’Euclide pour le pgcd dans Q[X]. Le cours se
termine en Section 3 sur un algorithme plus moderne, de complexité quasi-optimale,
exploitant la multiplication rapide. Ces algorithmes, à base d’approximants de Padé,
permettent aussi de calculer la reconstruction rationnelle, grâce à laquelle on peut
retrouver une récurrence linéaire à coefficients constants d’ordre d à partir de 2d
termes consécutifs d’une solution.
Dans ce cours, A désignera toujours un anneau intègre (commutatif et sans
diviseurs de zéro) et unitaire.

1. Algorithme d’Euclide
1.1. Le pgcd. Des pgcd peuvent être définis dans tout anneau intègre A : on
appelle plus grand diviseur commun (pgcd) de A et B tout G ∈ A qui divise A
et B et tel que tout diviseur de A et de B divise aussi G. Contrairement à l’usage,
nous notons dans ce cours pgcd(A, B) tout pgcd de A et de B sans faire de choix
de normalisation parmi les pgcd de A et de B.
L’algorithme d’Euclide présenté dans cette section permet le calcul du pgcd
dans Z ou dans l’anneau K[X], où K est un corps. Il repose sur l’existence d’une
division euclidienne dans ces anneaux. Un anneau intègre A est appelé anneau
euclidien s’il existe une fonction de taille d : A → N ∪ {−∞} telle que pour tout a ∈
93
94 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

Euclide(A,B)
Entrée : A et B dans A.
Sortie : Un pgcd de A et B.
1. R0 := A ; R1 := B ; i := 1.
2. Tant que Ri est non nul, faire :
Ri+1 := Ri−1 mod Ri
i := i + 1
3. Renvoyer Ri−1 .

Fig. 1. L’algorithme d’Euclide

A, b ∈ A \ {0}, il existe q et r dans A avec

a = qb + r, d(r) < d(b).
En particulier, d(0) < d(b) dès que b est non nul. Dans le cas des entiers, la valeur
absolue fournit une telle fonction d, et le degré remplit ce rôle pour les polynômes.
La notation r := a mod b sert dans les deux cas à définir r à partir de a et de b.
L’entier ou le polynôme r s’appelle le reste.
Exercice 1. Un élément d’un anneau est dit irréductible si les produits qui
lui sont égaux font tous intervenir un élément inversible. Tout anneau euclidien
est factoriel (c’est-à-dire que tout élément non nul y a une factorisation unique
en irréductibles, à l’ordre près de la factorisation et à des multiplications près des
facteurs par des inversibles de l’anneau). Le pgcd se lit aussi sur les factorisations.
Si A et B se factorisent sous la forme
A = am1k1 · · · mks s , B = bm!11 · · · m!ss ,
où a et b sont inversibles dans A, les mi sont irréductibles et les ki et !i sont des
entiers positifs ou nuls, montrer qu’alors un pgcd de A et B est
min(k1 ,!1 )
G = m1 · · · mmin(k
s
s ,!s )
.
Autrement dit, on « met » dans G les facteurs irréductibles communs de A et B,
avec la plus grande multiplicité possible. La factorisation dans Z ou dans K[X] est
plus coûteuse que le pgcd et cette propriété n’est donc pas utilisée pour le calcul
du pgcd.
1.2. Calcul du pgcd. Étant donnés A, B dans un anneau euclidien A, l’algo-
rithme d’Euclide (Fig. 1) calcule une suite de restes successifs dont la taille décroı̂t,
jusqu’à atteindre le pgcd.
La terminaison provient de la décroissance stricte de la taille à chaque étape.
La correction de cet algorithme se déduit de la relation
pgcd(F, G) = pgcd(H, G) pour H := F mod G,
dont la preuve est laissée en exercice. Par récurrence, il s’ensuit que pgcd(F, G) =
pgcd(Ri , Ri+1 ) pour tout i. Si en outre Ri+1 est nul, alors pgcd(Ri , Ri+1 ) = Ri , ce
qui prouve la correction.
 1. ALGORITHME D’EUCLIDE 95

Exemple 1. Soient A = X 4 − 13X 3 + 2X 2 − X − 1 et B = X 2 − X − 1 dans

Q[X]. La suite des restes est :
R0 = X 4 − 13X 3 + 2X 2 − X − 1,
R1 = X 2 − X − 1,
R2 = −22X − 10,
R3 = −41/121,
R4 = 0,
de sorte que −41/121 est un pgcd de A et B et donc 1 aussi.
Proposition 1. L’algorithme d’Euclide calcule un pgcd de A et B dans K[X]
en O(deg A deg B) opérations dans K.
Démonstration. La correction a été prouvée dans le cas général. Pour l’étude
de complexité, nous supposons d’abord que deg A ≥ deg B. D’après le cours 3
(p. 1.1), le calcul de P mod Q peut être effectué en 2 deg Q(deg P − deg Q + 1)
opérations de K. Il s’ensuit que le coût de l’algorithme d’Euclide est borné par la
somme des 2 deg(Ri )(deg Ri−1 − deg Ri + 1), pour i ≥ 1. Tous! les deg(Ri ) sont
majorés par deg A, de sorte que le coût est borné par 2 deg A i≥1 (deg Ri−1 −
deg Ri + 1) = 2 deg A(deg R0 + deg B) = O(deg A deg B).
Si le degré de B et supérieur à celui de A, la première étape ne coûte pas
d’opération arithmétique, et la borne ci-dessus s’applique ensuite au reste du calcul.
!
La borne de complexité quadratique reflète bien le comportement de l’algo-
rithme : dans une exécution typique de l’algorithme, les quotients ont degré 1 à
chaque itération, les degrés des restes successifs diminuent de 1 à chaque itération
et leur calcul est linéaire ; le nombre de coefficients intermédiaires calculés est qua-
dratique et ils sont calculés aussi efficacement qu’il est possible par un algorithme
qui les calcule tous.
1.3. Pgcd étendu et inversion modulaire.

Relation de Bézout. Une relation de la forme G = U A + V B qui donne le pgcd G

de deux polynômes A et B avec deux cofacteurs polynomiaux U et V est appelée
une relation de Bézout. L’algorithme d’Euclide étendu est une modification légère
de l’algorithme d’Euclide qui calcule non seulement le pgcd, mais aussi une relation
de Bézout particulière,
(1) U A + V B = G, avec d(U G) < d(B) et d(V G) < d(A).
Une fois le pgcd G choisi, les cofacteurs U et V sont rendus uniques par la contrainte
sur les degrés. Dans de nombreuses applications, c’est davantage de ces cofacteurs U
et V que du pgcd lui-même dont on a besoin. On parle alors de calcul de pgcd étendu.
Ce calcul intervient par exemple de manière importante dans les algorithmes de
factorisation de polynômes dans Z[X] ou Q[X] par des techniques de type « Hensel »
(cours 30), et dans le développement rapide des séries algébriques (cours 12).
Les calculs de pgcd étendu permettent d’effectuer des inversions modulaires.
Lorsque A et B sont premiers entre eux (G ∈ A), alors l’élément V est un inverse
de B modulo A.
96 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

Exemple 2. La relation de Bézout pour a + bX et 1 + X 2 s’écrit :

(a − bX)(a + bX) + b2 (1 + X 2 ) = a2 + b2 .

L’inverse de B = a + bX modulo A = 1 + X 2 vaut donc

a − bX
V = .
a2 + b2
Puisque le corps des complexes s’obtient par le quotient R[X]/(X 2 + 1), cette rela-
tion n’est autre que la formule d’inversion familière
1 a − ib
= 2 .
a + ib a + b2
Si A ∈ A est irréductible, A/(A) est un corps et le calcul de la relation de Bézout
permet d’y effectuer la division : si B '= 0 mod A alors N/B = N V mod A.

Exemple 3. La « simplification » de la fraction rationnelle

φ4 − φ + 1 25φ − 34
r= =
φ −1
7 169
où φ est le « nombre d’or », défini par A(φ) = 0 pour A(X) = X 2 − X − 1, est
obtenue par les trois calculs suivants :
– calcul du reste U = 13X + 7 par U := X 7 − 1 mod A,
– détermination de la relation de Bézout
13X − 20
(13X + 7) − A = 1,
169
– calcul du reste V = 25X − 34 par V := (13X − 20)(X 4 − X + 1) mod A.

Plus généralement, dans le cas où A ∈ K[X] est un polynôme irréductible, ces
calculs montrent que le corps K(α) des fractions rationnelles en α racine de A est un
espace vectoriel dont une base est 1, α, α2 , . . . , αdeg A−1 . Les algorithmes d’Euclide
et d’Euclide étendu fournissent un moyen de calcul dans cette représentation. Il est
ainsi possible de manipuler de manière exacte les racines d’un polynôme de degré
arbitraire sans « résoudre ».

Exemple 4. Lorsque l’élément A ∈ A n’est pas irréductible, A/(A) n’est pas

un corps. Cependant, les éléments inversibles peuvent y être inversés par le même
calcul que ci-dessus. Lorsqu’un élément B non nul n’est pas inversible, la relation
de Bézout se produit avec un G différent de 1. Il est alors possible de tirer parti
de cette information (un facteur de A) en scindant le calcul d’une part sur G et
d’autre part sur B/G.

Exemple 5. Le même calcul qu’à l’exemple 3 fonctionne sur des entiers :

25
r= ≡ 5 mod 7
33
se déduit de

33 mod 7 = 5, 3 × 5 − 2 × 7 = 1, 3 × 25 mod 7 = 5.
 2. RÉSULTANT 97

Euclide étendu(A,B)
Entrée : A et B dans A.
Sortie : Un pgcd de A et B et les cofacteurs U et V de l’identité de
Bézout U A + V B = G.
1. R0 := A ; U0 := 1 ; V0 := 0 ; R1 := B ; U1 := 0 ; V1 := 1 ; i := 1.
2. Tant que Ri est non nul, faire :
Ri+1 := QRi + Ri−1 la division euclidienne ;
Ui+1 := Ui−1 − QUi ; Vi+1 := Vi−1 − QVi ;
i := i + 1
3. Renvoyer Ri−1 , Ui−1 , Vi−1 .

Fig. 2. L’algorithme d’Euclide étendu

Calcul des cofacteurs. L’idée-clé est de suivre pendant l’algorithme d’Euclide la

décomposition de chacun des Ri sur A et B. Autrement dit, pour tout i, l’algorithme
calcule des éléments Ui et Vi tels que

Ui A + Vi B = Ri ,

dont les tailles sont bien contrôlées. Pour i = 0, il suffit de poser U0 = 1, V0 = 0, ce

qui correspond à l’égalité

1 · A + 0 · B = A = R0 .

Pour i = 1, l’égalité
0 · A + 1 · B = B = R1
est obtenue avec U1 = 0, V1 = 1. Ensuite, la division euclidienne

Ri−1 = QRi + Ri+1

donne la relation

Ri+1 = Ri−1 − QRi = (Ui−1 − QUi )A + (Vi−1 − QVi )

qui pousse à définir Ui+1 par Ui−1 − QUi et Vi+1 par Vi−1 − QVi , et à partir de
laquelle une preuve par récurrence montre que les conditions de tailles de la relation
de Bézout sont satisfaites.
L’algorithme est résumé en Figure 2. À nouveau, dans le cas des polynômes ou
des entiers, la complexité est quadratique.

2. Résultant
2.1. Matrice de Sylvester. L’algorithme d’Euclide pour deux polynômes
A, B à une variable est étroitement relié à la matrice de Sylvester. Si

A = am X m + · · · + a0 , B = bn X n + · · · + b0 ,
98 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

appartiennent à A[X], cette matrice carrée s’écrit

 
am am−1 ... a0
 a a . .. a0 
 m m−1 
 . . . . . . 
 
 am am−1 . . . a0 
Syl(A, B) =   bn bn−1 . . .


 b0 
 bn bn−1 . . . b0 
 
 ... ... 
bn bn−1 . . . b0
avec les n premières lignes contenant les coefficients de A et les m suivantes conte-
nant les coefficients de B.
La transposée de cette matrice représente l’application linéaire
(U, V ) *→ AU + BV,
en se limitant aux paires (U, V ) tels que deg U < deg B et deg V < deg A, et en uti-
lisant la base des monômes 1, X, . . . , X m+n−1 à l’arrivée. Les combinaisons linéaires
des lignes de la matrice de Sylvester donnent donc les coefficients des polynômes
qui peuvent être obtenus comme image. Au vu de la relation de Bézout (1), le pgcd
de A et B peut être obtenu ainsi et il est caractérisé comme l’élément de plus petit
degré qui peut l’être. Ceci permet de le lire sur une forme échelonnée en ligne de
la matrice.
Definition 1. Une matrice est en forme échelonnée en ligne lorsque
1. les lignes nulles sont toutes en dessous des lignes non nulles,
2. le premier coefficient non nul de chaque ligne non nulle est à droite du
premier coefficient non nul de la ligne précédente, les coefficients des lignes
suivantes dans sa colonne étant nuls.
L’algorithme classique d’élimination de Gauss sans pivot sur les colonnes calcule
une forme échelonnée en ligne d’une matrice, dont les lignes non nulles sont une base
de l’espace vectoriel engendré par les lignes de la matrice de départ. En conclusion,
nous avons obtenu une relation entre la matrice de Sylvester et le pgcd.
Proposition 2. Soient A, B deux polynômes de K[X]. Alors la forme
échelonnée en ligne de la matrice de Sylvester Syl(A, B) contient sur sa dernière
ligne non nulle les coefficients d’un pgcd de A et B. En outre, la dimension du
noyau de cette matrice est le degré du pgcd.
Exemple 6. Pour les polynômes A = X 4 − X 3 − 7X 2 + 2X + 3 et B =
X − 4X 2 + 2X + 3, la matrice de Sylvester et sa forme échelonnée en ligne sont :
3
   
1 −1 −7 2 3 0 0 1 −1 −7 2 3 0 0
0 1 −1 −7 2 3 0 0 1 −1 −7 2 3 0 
   
0 0 1 −1 −7 2 3  0 0 1 −1 −7 2 3 
   
1 −4 2 0 0 0  0 −14 45 −3 −18
 3  et 0 0 .
0 1 −4 2 3 0 0  0 0 0 0 − 5 12 9 
   7 7 7 
0 0 1 −4 2 3 0 0 0 0 0 0 1 3 
− 10
10
0 0 0 1 −4 2 3 0 0 0 0 0 0 0
La dernière ligne non nulle donne le pgcd X − 3.
 2. RÉSULTANT 99

Fig. 3. Le résultant calcule des projections

Definition 2. Le résultant de A et B est le déterminant de la matrice de

Sylvester Syl(A, B). Il est noté Res(A, B) ou ResX (A, B) si l’on veut insister sur
l’élimination de la variable X.
Le résultant peut être vu comme une condition de cohérence pour le système
formé par les deux polynômes A et B.
Corollaire 1. Soient A et B deux polynômes de K[X]. Alors A et B sont
premiers entre eux si et seulement si Res(A, B) '= 0.
Démonstration. Le déterminant d’une matrice carrée se lit sur la forme
échelonnée en ligne en faisant le produit des éléments diagonaux. Il est non nul
si et seulement si tous les éléments diagonaux le sont et dans ce cas un pgcd non
nul est sur la dernière ligne. À l’inverse, s’il existe un pgcd G non nul, alors les
polynômes X k G montrent l’existence de lignes avec un coefficient de tête non nul
dans chaque colonne de la forme échelonnée. !
Exemple 7. Le discriminant de A est par définition le résultant de A et sa
dérivée A# . Il s’annule lorsque ces deux polynômes ont une racine commune dans
une clôture algébrique de A, c’est-à-dire, en caractéristique nulle, lorsque A a une
racine multiple.
Exercice 2. Calculer le discriminant de aX 2 +bX+c en prenant le déterminant
de la matrice de Sylvester.
2.2. Applications du résultant.

Calculs de projections. Algébriquement, la « résolution » d’un système polyno-

mial se ramène souvent à une question d’élimination. Lorsqu’elle est possible,
l’élimination successive des variables amène le système d’entrée sous une forme
triangulaire. De proche en proche, la résolution d’un tel système se réduit alors à
la manipulation de polynômes à une variable, pour lesquels compter, isoler, . . . , les
solutions est bien plus facile.
Géométriquement, l’élimination correspond à une projection. Cette section
montre comment le résultant de deux polynômes permet de traiter ce genre de
problèmes, pour les systèmes de deux équations en deux inconnues. Le schéma
général est représenté en Figure 3. Cette opération est à la base d’une technique
100 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

Fig. 4.

plus générale pour un nombre arbitraire d’équations et d’inconnues, la résolution

géométrique, qui sera présentée au cours 20.
Exemple 8. Les deux courbes de la Figure 4 ont pour équations
A = (X 2 + Y 2 )3 − 4X 2 Y 2 = 0, B = X 2 (1 + Y ) − (1 − Y )3 = 0.
Ces deux polynômes sont irréductibles et leur pgcd qui vaut 1 ne renseigne pas sur
leurs racines communes. Les résultants par rapport à X et Y donnent en revanche
des polynômes qui s’annulent sur les coordonnées de ces points d’intersection :
ResX (A, B) = (4Y 7 + 60Y 6 − 152Y 5 + 164Y 4 − 95Y 3 + 35Y 2 − 9Y + 1)2 ,
ResY (A, B) = 16X 14 + 6032X 12 − 1624X 10 + 4192X 8 − 815X 6 − 301X 4 − 9X 2 + 1.
Il n’y a que 4 points d’intersection visibles sur la figure, les 10 autres ont au moins
une coordonnée qui n’est pas réelle. Le caractère bicarré du résultant en Y provient
de la symétrie de la figure par rapport à l’axe des Y . C’est pour cette même raison
que le premier résultant est un carré.
Le résultat général est le suivant.
Proposition 3. Soit A = am Y m + · · · et B = bn Y n + · · · où les coefficients
ai et bj sont dans K[X]. Alors les racines du polynôme ResY (A, B) ∈ K[X] sont
d’une part les abscisses des solutions du système A = B = 0, d’autre part les racines
communes de am et bn .
Démonstration. Ce résultat est une conséquence immédiate du théorème 1
de la section 2.3 ci-dessous. !

Graphiquement, les racines « dégénérées » du second cas se traduisent par la

présence d’asymptotes verticales.
Exemple 9. Avec A = X 2 Y + X + 1, B = XY − 1, on obtient ResY (A, B) =
−X(2X + 1) (asymptote en X = 0, « vraie » solution en X = − 12 ). Les courbes
correspondantes sont représentées en Figure 5.
 2. RÉSULTANT 101

Fig. 5.

Une fois calculé le résultant donnant les coordonnées des abscisses des intersec-
tions des deux courbes, il est souhaitable d’obtenir les ordonnées correspondantes.
Dans le cas simple où l’avant dernier reste de l’algorithme d’Euclide est de degré 1,
il donne une telle paramétrisation.
Exemple 10. Sur les deux polynômes A et B de l’exemple 8, vus comme
polynômes dans Q(X)[Y ], la suite des restes est
(X 4 − 13X 2 + 15)Y 2 − 4(X 2 + 2)(X 2 + 3)Y + (X 6 − 2X 4 − 8X 2 + 10),
(4X 8 − 344X 6 − 1243X 4 − 301X 2 − 21)Y + (84X 8 − 372X 6 + 169X 4 + 143X 2 + 15),
1.
Un calcul de pgcd du coefficient de Y dans l’avant dernier reste avec ResY (A, B)
montre que ces deux polynômes sont premiers entre eux. Pour chaque racine X
de ResY (A, B) il y a donc un unique point d’intersection aux deux courbes, d’or-
donnée donnée par
84X 8 − 372X 6 + 169X 4 + 143X 2 + 15
Y =− .
4X 8 − 344X 6 − 1243X 4 − 301X 2 − 21
En utilisant un calcul de pgcd étendu, ceci peut être récrit comme expliqué plus
haut en un polynôme de degré au plus 13 en X.
Le même calcul sur A et B vus comme polynômes dans Q(Y )[X] donne B
comme dernier reste avant le pgcd. Ceci correspond aux deux points ayant la même
projection sur l’axe des Y .

Implicitation. Une autre application géométrique du résultant est l’implicitation

de courbes du plan. Étant donnée une courbe paramétrée
X = A(T ), Y = B(T ), A, B ∈ K(T ),
il s’agit de calculer un polynôme non trivial en X et Y qui s’annule sur la courbe. Il
suffit pour cela de prendre le résultant en T du numérateur de X −A(T ) et Y −B(T ).
Exemple 11. La courbe « en fleur » de la Figure 4 peut aussi être donnée sous
la forme
4t(1 − t2 )2 8t2 (1 − t2 )
X= , Y = .
(1 + t2 )3 (1 + t2 )3
102 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

Il suffit d’effectuer le calcul du résultant

Rest ((1 + t2 )3 X − 4t(1 − t2 )2 , (1 + t2 )3 Y − 8t2 (1 − t2 ))
pour retrouver (à un facteur constant près) le polynôme A de l’exemple 8.
2.3. Propriétés. L’essentiel des propriétés du résultant est contenu dans le
théorème suivant.
Théorème 1. Si les polynômes A et B de A[X] s’écrivent
A = a(X − α1 ) · · · (X − αm ), B = b(X − β1 ) · · · (X − βn ),
alors, le résultant de A et B vaut
( ( (
Res(A, B) = an bm (αi −βj ) = (−1)mn bm A(βi ) = an B(αi ) = (−1)mn Res(B, A).
i,j 1≤i≤n 1≤i≤m

Démonstration. Il suffit de prouver la première égalité. Les deux suivantes

en sont des conséquences immédiates.
Le facteur an bm est une conséquence de la multilinéarité du déterminant.
Nous considérons maintenant le cas où a = b = 1. Il est commode de considérer
le cas générique où les αi et βj sont des indéterminées et où l’anneau A est
Z[α1 , . . . , αm , β1 , . . . , βn ]. Si le résultat est vrai dans cet anneau, il l’est aussi pour
des valeurs arbitraires des αi et βj . Le corollaire 1 dans Q(α1 , . . . , αm , β1 , . . . , βn )
montre que le produit des αi − βj divise le résultant. Par ailleurs, le degré en αi
de chacune des n premières lignes de la matrice de Sylvester est 1 et ce degré est
nul pour les m autres lignes. Ceci donne une borne n pour le degré en chaque αi
du résultant et de la même manière une borne m pour son degré en chaque βj . Il
s’ensuit que le résultant est égal au produit des αi − βj à un facteur constant près.
Ce facteur est indépendant des αi et βj . En choisissant β1 = · · · = βn = 0, c’est-
à-dire B = X n , et en développant le déterminant par rapport à ses m dernières
lignes, on obtient que le résultant vaut (−1)mn A(0)n , ce qui donne le facteur 1 et
conclut la preuve. !

Corollaire 2 (Multiplicativité du résultant). Pour tous polynômes A, B, C

de A[X], Res(AB, C) = Res(A, C) Res(B, C).
Démonstration. L’anneau A est intègre, il possède donc un corps de frac-
tion qui a lui-même une clôture algébrique dans laquelle les polynômes A, B et C
peuvent s’écrire sous la forme utilisée dans le théorème précédent. L’identité sur les
résultants (qui appartiennent à A par définition) est alors vérifiée en considérant
les produits deux à deux de racines. !

Une dernière propriété utile du résultant est la suivante.

Proposition 4. Il existe U et V dans A[X] tels que le résultant s’écrive S =
U A + V B.
Démonstration. En ajoutant à la dernière colonne de la matrice de Sylves-
ter le produit des colonnes précédentes par des puissances adaptées de X, on fait
apparaı̂tre dans la dernière colonne les polynômes A et B, sans avoir changé le
déterminant. Le développement du déterminant par rapport à la dernière colonne
permet alors de conclure. !
 2. RÉSULTANT 103

L’algorithme d’Euclide étendu montre que S (qui est un multiple par un élément
du corps des fractions K de l’un des restes euclidiens « standards »), peut s’écrire
comme une combinaison polynomiale de A et B, à coefficients dans K[X]. Cette
proposition montre que cette combinaison se fait « sans division », c’est-à-dire avec
des coefficients dans A[X].
2.4. Calcul avec des nombres algébriques. L’idée que les polynômes sont
des bonnes structures de données pour représenter leur racines amène à chercher
des algorithmes pour effectuer les opérations de base sur ces racines, comme la
somme ou le produit. Le résultant répond à cette attente.
) )
Proposition 5. Soient A = i (X − αi ) et B = j (X − βj ) des polynômes
de K[X]. Alors
(
ResX (A(X), B(T − X)) = (T − (αi + βj )),
i,j
(
ResX (A(X), B(T + X)) = (T − (βj − αi )),
i,j
(
ResX (A(X), X deg B
B(T /X)) = (T − αi βj ),
i,j
(
ResX (A(X), T − B(X)) = (T − G(fi )).
i

Démonstration. C’est une application directe du Théorème 1. !

√ √
Exemple 12. On sait que 2 est racine de X 2 − 2, tout comme√ √ 3 est racine
de X 2 − 3. Un polynôme de degré minimal ayant pour racine 2 + 3 est donné
par
ResX (X 2 − 2, (T − X)2 − 3) = T 4 − 10T 2 + 1.
Ces opérations ne distinguent
√ √ pas les racines de A et B, les quatre racines du
résultant sont donc ± 2 ± 3.

Calcul du résultant bivarié. On dispose à l’heure actuelle d’un algorithme rapide

(quasi-optimal) pour le calcul du résultant univarié. Le meilleur algorithme connu
actuellement pour le calcul du résultant bivarié est une méthode d’évaluation-
interpolation qui se ramène au résultant univarié. Cet algorithme n’est pas quasi-
optimal. En revanche, pour les trois premières opérations de la Proposition 5, des
algorithmes quasi-optimaux à base de multiplication rapide de séries existent, ils
ont été présentés dans le cours 3.
2.5. % Sous-résultants %.

La croissance des coefficients dans l’algorithme d’Euclide. Le nombre d’opérations

dans le corps des coefficients n’est pas une mesure suffisante de la complexité des
calculs lorsque les opérations elles-mêmes ont une complexité variable. C’est le cas
pour le calcul de pgcd dans Q[X] et dans K(Y )[X]. Dans ces corps de coefficients,
on constate empiriquement les phénomènes suivants :
– l’algorithme d’Euclide amène à faire des divisions, et introduit des
dénominateurs au cours du calcul ;
104 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

– la taille des coefficients croı̂t rapidement ;

– ces coefficients peuvent souvent se « simplifier ».
Exemple 13. L’exécution de l’algorithme d’Euclide sur
A = 115X 5 + 7X 4 + 117X 3 + 30X 2 + 87X + 44,
B = 91X 4 + 155X 3 + 3X 2 + 143X + 115.
produit les restes successifs suivants :
3601622 3 1196501 2 151912 2340984
X − X + X+
8281 8281 637 8281
189886027626841 2 57448278681703 17501090665331
X − X−
12971681030884 3242920257721 3242920257721
3748556212578804983806085060 141833360915123969328014892
X+ .
4354148470945709877351001 334934497765054605950077
En simplifiant ces restes par des multiplications par des constantes bien choisies,
on obtient les restes :
3601622X 3 − 1196501X 2 + 1974856X + 2340984,
22930325761X 2 − 27749440252X − 8453612204,
288979986761465X + 142143002707719.
Il est souhaitable d’éviter le calcul sur les rationnels ou les fractions rationnelles
pour lequel l’addition requiert des calculs de multiplications et éventuellement de
pgcd. Une première idée consiste alors à éviter totalement les divisions en utilisant
des pseudo-restes.
Definition 3. Si A et B sont des polynômes de A[X] et b est le coefficient de
tête de B, le pseudo-reste R de A et B est défini par
bdeg A−deg B+1 A = QB + R.
Remplacer les calculs de restes de l’algorithme d’Euclide par des calculs de
pseudo-restes évite d’introduire des dénominateurs. Cette idée seule n’est pas suf-
fisante : les coefficients de ces pseudo-restes croissent trop.
Exemple 14. Sur le même exemple, la modification de l’algorithme d’Euclide
produit la suite de pseudo-restes
3601622X 3 − 1196501X 2 + 1974856X + 2340984,
189886027626841X 2 − 229793114726812X − 70004362661324,
257057096083899261191107914552182660X
+126440823512296156588839626542149756.
Une possibilité pour éviter cette croissance est de diviser ces polynômes par le
pgcd de leurs coefficients à chaque étape. C’est ce que nous avons fait dans l’exemple
ci-dessus. On parle alors de suite de pseudo-restes primitifs. Cependant, ces calculs
de pgcd de coefficients sont trop coûteux.
L’algorithme des sous-résultants donné en Figure 6 est une modification de
l’algorithme d’Euclide qui évite les divisions, tout en prévoyant des facteurs com-
muns qui apparaissent dans les coefficients de la suite des pseudo-restes de sorte à
limiter leur croissance. Ces pseudo-restes sont appelés des sous-résultants. Dans cet
algorithme, on se contente de renvoyer le dernier sous-résultant non nul ; on conçoit
 2. RÉSULTANT 105

Sous-résultants(A,B)
Entrée : A et B dans A[X] avec deg B < deg A.
Sortie : Le dernier sous-résultant non nul.
1. f = g = s = 1
2. Tant que deg B > 0
(a) d = deg A − deg B
(b) R =pseudoReste(A, B)
(c) Si les degrés de A et B sont impairs, faire s = −s.
(d) Faire A := B et mettre dans B le quotient de la division
de R par f g d
(e) Prendre f :=coefficientDominant(A)
(f) Mettre à jour g en lui affectant le quotient de la division
de f d par g d−1
3. d = deg A ;
4. Renvoyer le quotient de la division de sB d par g d−1 .

Fig. 6.

aisément comment modifier l’algorithme pour obtenir n’importe quel sous-résultant

(spécifié par des conditions de degré, par exemple).

Exemple 15. Toujours sur les même polynômes, la suite des sous-résultants
redonne les polynômes que nous avions déjà calculés par simplification :
3601622X 3 − 1196501X 2 + 1974856X + 2340984,
22930325761X 2 − 27749440252X − 8453612204,
288979986761465X + 142143002707719.
La suite des sous-résultant de cet exemple est donc primitive : les facteurs prédits
par l’algorithme du sous-résultant ont suffi à éliminer tout facteur commun entre
les coefficients des pseudo-restes.

Comme le résultant, les sous-résultants sont liés à la matrice de Sylvester et à

l’algorithme d’Euclide. Une formule de Cramer sur une sous-matrice de la matrice
de Sylvester donne le résultat suivant.

Proposition 6. Toutes les divisions effectuées au cours de l’algorithme des

sous-résultants sont exactes.

La preuve de ce résultat est technique et omise ici.

En corollaire, on remarque en outre qu’il est assez facile de déduire de ce résultat
des estimations sur la « taille » des coefficients qui apparaissent au cours de l’al-
gorithme. Un cas particulier intéressant est celui où A est l’anneau de polynômes
K[Y ]. Alors, si A et B ont des degrés totaux m et n, tous les sous-résultants ont des
degrés bornés par mn. Ces bornes permettent un calcul du résultant par évaluation-
interpolation dès que l’on dispose d’un algorithme efficace dans le cas univarié.
106 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

Fig. 7.

Calcul de la paramétrisation. Les sous-résultants permettent de finir la

« résolution » des systèmes de deux polynômes bivariés. Pour simplifier, nous faisons
l’hypothèse que pour tout x racine du résultant R = ResY (A, B), il n’y a qu’un seul
y tel que A(x, y) = B(x, y) = 0. Dans ce cas, on peut montrer que le sous-résultant
S1 (de degré 1 en Y ) est non nul ; écrivons-le sous la forme S1 = P0 (X)Y + Q0 (X).
Comme pour le résultant, il existe des polynômes U et V dans K[X, Y ] tels qu’on
ait l’égalité
AU + BV = P0 (X)Y + Q0 (X).
On en déduit donc que toutes les solutions (x, y) du système A = B = 0 satis-
font l’équation P0 (x)y = Q0 . Autrement dit, en écartant les solutions dégénérées
où P0 (x) = 0, on obtient l’ordonnée des points solutions en évaluant la fraction
rationnelle −Q0 /P0 sur les racines du résultant R. Autrement dit, cette procédure
permet de décrire les solutions du système sous la forme
*
y = Q(x)
R(x) = 0
Géométriquement, ce polynôme Q permet de retrouver y à partir de x, il permet
donc d’effectuer l’opération symbolisée sur la Figure 7, la paramétrisation des so-
lutions du système par les racines de R.
Exemple 16. Sur les mêmes polynômes qu’à l’exemple 8, le sous-résultant
redonne la paramétrisation calculée à partir de l’algorithme d’Euclide, mais en
étant plus économe dans les opérations sur les coefficients.

3. Approximants de Padé-Hermite et algorithmes efficaces

3.1. Définitions.
Definition 4. Un approximant de Padé de type (m, n) d’une série S ∈ K[[X]]
est une fraction rationnelle R ∈ K(X) dont le numérateur a degré borné par m le
dénominateur a degré borné par n et telle que
R − S = O(X m+n+1 ).
Definition 5. Un approximant de Padé-Hermite de type m1 , . . . , mk d’un k-
uplet de séries S1 , . . . , Sk de K(X) est un k-uplet de polynômes p1 , . . . , pk de K[X]
tels que deg pi ≤ mi , i = 1, . . . , k et
p1 S1 + · · · + pk Sk = O(X m1 +···+mk +k−1 ).
 3. APPROXIMANTS DE PADÉ-HERMITE ET ALGORITHMES EFFICACES 107

Les approximants de Padé sont obtenus comme cas particulier des approximants
de Padé-Hermite en prenant le couple de séries (1, S).
3.2. Applications.

Reconstruction rationnelle. Si la série S provient du développement d’une fraction

rationnelle P/Q, alors le calcul d’approximant de Padé à partir de suffisamment de
termes de la série reconstruit cette fraction. En effet, si A/B est un approximant
de type (deg P, deg Q), l’identité
A P
= S + O(X deg P +deg Q+1 ) = + O(X deg P +deg Q+1 )
B Q
entraı̂ne
AQ = BP + O(X deg P +deg Q+1 ).
Le degré des polynômes intervenant dans cette égalité est borné par deg P + deg Q.
Il s’ensuit que cette identité de séries est une identité de polynômes :
AQ = BP.
Les applications de cette propriété sont nombreuses : pour la résolution de
systèmes différentiels à coefficients constants (cours 8), pour reconnaı̂tre une suite
récurrente linéaire à partir de ses premiers termes, pour le calcul de polynômes
minimaux de matrices creuses par l’algorithme de Wiedemann (cours 27), pour
la résolution de systèmes linéaires à coefficients polynomiaux (cours 28), pour le
décodage des codes BCH en théorie des codes, etc.

Pgcd. Si A et B sont des polynômes de K[X] de degrés m et n, il existe un

approximant de Padé non nul de A/B type (n − 1, m − 1) si et seulement si A
et B ont un pgcd non trivial. Dans ce cas, l’élément de degré minimal de la base
renvoyée par l’algorithme du Théorème 2 fournit deux polynômes U et V tels que
U A + V B = 0,
où l’égalité à 0 provient à nouveau de considérations de degré.
Il s’ensuit que
A V
=−
B U
et par conséquent le pgcd vaut A/V = B/U .

Pgcd étendu. Une fois trouvé le pgcd, l’identité de Bézout

UA + V B − G = 0
s’obtient par un approximant de Padé-Hermite de type (n−1, m−1, 0) de (A, B, G),
à nouveau dans la même complexité.
À l’inverse, il est possible de calculer des approximants de Padé à partir de
l’algorithme d’Euclide étendu.
Proposition 7. Soit Ri la suite des restes associés à X n et F = F mod X n .
Soit i le premier indice tel que deg Ri ≤ m − 1, et Ai , Bi les cofacteurs correspon-
dant :
Ai X n + Bi F = Ri .
108 10. PGCD, RÉSULTANT, ET APPROXIMANTS DE PADÉ

Il existe une solution au problème de Padé (m, n − m) si et seulement si

pgcd(Ri , Bi ) = 1. Si c’est le cas, tous les approximants (m, n − m) sont proportion-
nels au couple (Ri , Bi ).
3.3. Calcul. Le problème du calcul d’approximants de Padé-Hermite est un
problème d’algèbre linéaire : les coefficients de 1, X, X 2 , . . . , X m1 +···+mk +k−2 four-
nissent un système linéaire (homogène) en les coefficients de p1 , . . . , pk — c’est
d’ailleurs cette réécriture qui sous-tend le choix de l’ordre de troncature : il y a
autant d’équations que d’inconnues (à la constante d’homogénéité près : p1 , . . . , pk
ne peuvent être déterminés qu’à une constante près).
Davantage que de savoir si le problème a une solution, la question est donc
plutôt ici de trouver cette solution rapidement : on veut faire mieux que la résolution
brutale d’un système linéaire.
Il se trouve que l’on dispose d’un algorithme quasi-optimal, dont l’efficacité
est utilisée dans ce cours comme la base de nombreux algorithmes efficaces. La
constante dans le O(·) peut être améliorée dans le cas du pgcd et du pgcd étendu,
mais il est plus simple pédagogiquement de se reposer sur une seule construction.
Théorème 2. Soit N = m1 + · · · + mk + k − 1. Il est possible de calculer
une base des approximants de Padé-Hermite sur K[X] en O(k ω M(N )) opérations
dans K.
L’algorithme repose sur un diviser pour régner assez subtil.
En corollaire, on obtient des algorithmes quasi-optimaux pour le calcul de pgcd
et de pgcd étendus de polynômes.

Notes
Pour le résultant de deux polynômes (et les sous-résultants), on peut consul-
ter [7, 1, 2] ou [3] pour une approche un peu plus complète. De nombreuses
propriétés des résultants et de l’algorithme d’Euclide sont établies de manière
élémentaire à l’aide des fonctions symétriques dans [4].
Le pgcd et le pgcd étendu peuvent aussi être définis dans un contexte non-
commutatif. Ils sont alors utiles au calcul avec des opérateurs différentiels ou de
récurrence. Cette généralisation sera présentée au cours 24.

Bibliographie
[1] Geddes (Keith O.), Czapor (Stephen R.), and Labahn (George). – Algorithms for Computer
Algebra. – Kluwer Academic Publishers, .
[2] Knuth (Donald E.). – The Art of Computer Programming. – Addison-Wesley Publishing Co.,
Reading, Mass., , 3rd edition, Computer Science and Information Processing, vol. 2 :
Seminumerical Algorithms, xiv+762p.
[3] Lang (Serge). – Algebra. – Springer-Verlag, New York, , third edition, Graduate Texts in
Mathematics, vol. 211, xvi+914p.
[4] Lascoux (Alain). – Symmetric functions and combinatorial operators on polynomials. – Publi-
shed for the Conference Board of the Mathematical Sciences, Washington, DC, , CBMS
Regional Conference Series in Mathematics, vol. 99, xii+268p.
[5] Pan (V. Y.) and Wang (X.). – Acceleration of Euclidean algorithm and extensions. In Mora
(Teo) (editor), ISSAC’2002. pp. 207–213. – ACM, New York, . Proceedings of the 2002 In-
ternational Symposium on Symbolic and Algebraic Computation, July 07–10, 2002, Université
de Lille, France.
 Bibliographie 109

[6] Stehlé (D.) and Zimmermann (P.). – A binary recursive Gcd algorithm. In ANTS-VI. Lecture
Notes in Computer Science, vol. 3076, pp. 411–425. – Springer, .
[7] von zur Gathen (Joachim) and Gerhard (Jürgen). – Modern computer algebra. – Cambridge
University Press, New York, , 2nd edition, xiv+785p.
[8] Yap (Chee). – Fundamental Problems in Algorithmic Algebra. – Oxford University Press, .