Algorithme d’Euclide
François DE M ARÇAY
Département de Mathématiques d’Orsay
Université Paris-Sud, France
1. Division euclidienne : École élémentaire
Soit Z l’anneau des nombres entiers naturels positifs ou négatifs, et soit N = Z+ ⊂ Z le
sous-ensemble des entiers qui sont positifs.
Définition 1.1. Diviser avec reste un entier a > 1 par un entier 1 6 b 6 a qui lui est
inférieur, cela consiste à trouver un quotient entier q > 0 et un reste entier r > 0 tels que :
a = q b + r,
le quotient q étant maximal possible, de telle sorte que dans le reste r, on ne puisse plus
extraire « du b » :
0 6 r 6 b − 1.
Il est bien connu que diviser avec reste est toujours possible, le couple (q, r) ∈ N × N
étant alors déterminé de manière unique en partant de a > 1 et de b avec 1 6 b 6 a
quelconques.
Exemple 1.2. Comme à l’école élémentaire, soit à diviser a = 126 par b = 35 :
126 35
− 105 3
21
Mentalement, on essaie de multiplier 35 successivement par 1, 2, 3, 4, et on trouve que
3 × 35 = 105 est le résultat maximum qui demeure inférieur à 126. On reporte alors − 105
à gauche, on soustrait 126 − 105 = 21, et on trouve :
|{z} 3 · |{z}
126 = |{z} 35 + |{z}
21 .
a q b r
Cet exemple s’inscrit dans un contexte général, connu depuis la Préhistoire sur Terre,
sur Mars, sur Jupiter, sur Vénus, et sans doute aussi sur quelques exoplanètes dotées de
mathématiques encore embryonnaires.
1
2 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
Théorème 1.3. [Division euclidienne des entiers] Étant donné deux nombres entiers po-
sitifs quelconques a ∈ N∗ et b ∈ N∗ avec 1 6 b 6 a, il existe toujours un entier positif
unique q ∈ N∗ et un entier positif unique r ∈ N — parfois égal à 0 — tels que :
a = qb+r et 06r<b
Exercice 1. En s’inspirant de la figure située à droite du portrait d’Euclide, expliquer en quoi la division
possède un sens géométrique.
2. Division euclidienne : polynômes à coefficients entiers
La division euclidienne fonctionne de manière essentiellement analogue dans l’anneau
Z[x] des polynômes à une indéterminée x et à coefficients entiers, sachant que plusieurs
opérations de soustraction successives s’avèrent nécessaires.
Exemple 2.1. Soit le polynôme quartique :
A(x) := 3 x4 + 2 x3 + x + 5,
à diviser avec reste par le polynôme quadratique (donc de degré inférieur) :
B(x) := x2 + 2 x + 3,
les deux monômes de tête de A et de B étant placés en première position. On se convainc
mentalement que c’est la multiplication par le monôme 3 x2 qui permet de faire monter le
monôme de tête de B(x) à ce nouveau niveau de celui de A(x) :
3 x4 = 3 x2 · x2 ,
et donc, on est conduit à soustraire :
A(x) − 3 x2 B(x) ,
| {z }
−3x4 −6x3 −9x2
procédé que l’on peut aussi représenter agréablement sous forme d’un tableau incomplet
qui commence à se remplir :
3 x4 + 2 x3 + 0 + x + 5 x2 + 2 x + 3
− 3 x4 − 6 x3 − 9 x2 3 x2
− 4 x3 − 9 x2 + x + 5
3. Division euclidienne : polynômes à coefficients dans un anneau 3
De cette manière, on fait apparaître le reste intermédiaire :
− 4 x3 − 9 x2 + x + 5,
qui possède un nouveau monôme de tête − 4 x3 , de telle sorte que c’est maintenant le
monôme multiplicateur :
−4x
qui permet de faire remonter le monôme de tête x2 de B(x) au niveau − 4 x3 .
Après itération et épuisement de ces calculs, le tableau final s’écrit :
3 x 4 + 2 x3 + 0 + x + 5 x2 + 2 x + 3
− 3 x4 − 6 x3 − 9 x2 3 x2
− 4 x3 − 9 x2 + x + 5
4 x3 + 8 x2 + 12 x −4x
− x2 + 13 x + 5
x2 + 2 x + 3 −1
15 x + 8
3 x2 − 4 x − 1
Ce tableau synoptique permet alors de lire instantanément le quotient et le reste dans la
division du polynôme A(x) par le polynôme B(x) :
A(x) = Q(x) ·B(x) + R(x),
| {z } | {z }
quotient reste
équation qui s’écrit donc explicitement :
3 x4 + 2 x3 + x + 5 = 3 x2 − 4 x − 1 · x2 + 3 x + 3 + 15 x + 8.
Bien entendu, ce deuxième exemple simple suggère aussi un procédé général, probable-
ment déjà connu du lecteur-étudiant.
3. Division euclidienne : polynômes à coefficients dans un anneau
Afin d’embrasser la division euclidienne dans un cadre algébrique adapté, nous travaille-
rons maintenant avec un anneau commutatif :
A , +, × ,
possédant un élément unité 1 ∈ A pour la multiplication :
1·r =r·1=r (∀ r ∈ A ),
la multiplication étant souvent notée « · » à la place de « × », voire même sous-entendue en
omettant tout symbole.
Définition 3.1. Un élément u ∈ A est appelé une unité s’il existe u0 ∈ A tel que :
u u0 = u0 u = 1,
et le groupe (multiplicatif, commutatif) des unités de A est alors noté A × .
4 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
Soit maintenant x un symbole qui désigne une indéterminée. L’espace vectoriel des
polynômes à coefficients dans A :
n o
A [x] := an xn + an1 xn−1 + · · · + a1 x + a0 : n ∈ N, an , an−1 , . . . , a1 , a0 ∈ A ,
est à nouveau un anneau commutatif possédant la même unité 1 ∈ A (exercice de révision
mentale).
Supposons temporairement pour simplifier que les polynômes :
B(x) = bm xm + bm−1 xm−1 + · · · + b0 (m > 0),
par lesquels on cherche à diviser d’autres polynômes :
A(x) = an xn + an−1 xn−1 + · · · + a0 (n > 0), ,
de degré supérieur n > m ont toujours un coefficient de tête bm ∈ A × qui est une unité.
Définition 3.2. Étant donné un polynôme de degré k > 0 :
P (x) = ck xk + ck−1 xk−1 + · · · + c0 (ck 6= 0),
on appelle monôme de tête de P son terme de plus haut degré et on le note :
Tete P (x) = ck xk .
Algorithme: Division polynomiale avec reste
• Entrées : Deux polynômes
X X
A(x) = ai x i et B(x) = bj x j
06i6n 06j6m
à coefficients ai ∈ A et bj ∈ A de degrés respectifs n > m > 1 tels que le
coefficient bm ∈ A × du monôme de tête bm xm de B(x) est une unité de l’anneau
A.
• Sorties : Un polynôme-quotient Q ∈ A [x] et un polynôme-reste R ∈ A [x] satis-
faisant :
A = Q B + R,
le degré de R étant strictement inférieur à celui de B :
0 6 deg R < m.
• Algorithme :
R ←−[ A.
pour i = n − m, n − m − 1, . . ., 0, faire :
si deg R = m + i alors Qi ←−[ Tete (R) bm
R ←−[ R − Qi B
sinon Qi ←−[ 0
P
Retourner Q = 06i6n−m Qi et R.
Ici, le lecteur-étudiant est invité à déchiffrer soigneusement les instructions de cet algo-
rithme, afin premièrement de se convaincre par la réflexion qu’il correspond bien à la si-
tuation générale exemplifiée ci-dessus, et deuxièmement, afin de reconstituer par lui-même
4. Anneaux intègres euclidiens 5
les arguments qui démontrent le caractère bien-fondé des calculs, et notamment, de vérifier
que l’algorithme termine en temps fini.
Contentons-nous de détailler la démonstration d’un lemme plus simple.
Lemme 3.3. [Unicité du quotient et du reste] Lorsque le coefficient bm ∈
mathcalA× du monôme de tête bm xm de B(x) est une unité, le polynôme-quotient Q(x)
et le polynôme-reste R(x) dans la division de A(x) par B(x) :
A = Q B + R,
sont déterminés de manière unique.
Démonstration. En effet, une autre équation :
A = Q0 B + R0 ,
soustraite à A = Q B + R donne après réorganisation :
Q0 − Q B = R − R 0 ,
et comme le membre de droite est de degré 6 degB − 1, le membre de gauche ne peut
qu’être identiquement nul, d’où Q0 = Q puis R0 = R.
4. Anneaux intègres euclidiens
Pourrait-on, par une conceptualisation adéquate, capturer dans un seul filet les deux
situations analogues classiques que sont :
• la division euclidienne dans N ou dans Z ;
• la division euclidienne dans Z[x] ou dans Q[x] ?
Dans les deux cas, ce qui compte, c’est l’existence d’une fonction naturelle qui mesure
l’abaissement de la complexité ou de la taille des objets après une division élémentaire.
Définition 4.1. [Anneaux euclidiens] Un anneau commutatif intègre A muni d’une unité
1 ∈ A est appelé un anneau euclidien s’il existe une fonction :
δ: A \{0} −→ N, δ(0) := −∞,
telle que, pour tous a, b ∈ A avec b 6= 0, il est possible de diviser a par b avec un reste
δ-inférieur au sens précis où :
il existe q, r ∈ A avec δ(r) < δ(b) satisfaisant a = q b + r .
Bien que l’unicité de q et celle de r ne soient pas requises dans cette définition, on dit
souvent que q est le quotient dans la division de a par b, et que r en est le reste.
Noter que la fonction δ est soumise à la seule condition de diriger les « abaissements de
complexité » δ(r) < δ(b).
Terminologie 4.2. On dira que δ est la fonction euclidienne de l’anneau euclidien (A , δ).
Avec la fonction valeur absolue δ(a) := |a|, il est bien connu que l’anneau des entiers
naturels Z est un anneau euclidien, et d’ailleurs, l’unicité du quotient q et du reste r sont
garanties dès lors qu’on demande que r > 0, ce qu’il est raisonnable de faire.
6 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
Lorsque A = K[x] est l’anneau des polynômes sur un corps, la fonction degré
d(a) := deg a, avec deg(0) := −∞, est la fonction naturelle qui munit K[x] d’une structure
d’anneau euclidien, l’unicité du quotient et du reste étant faciles à vérifier.
Rappelons qu’un élément p ∈ A divise un autre élément q ∈ A s’il existe r ∈ A
satisfaisant :
p = r q.
Définition 4.3. [Plus grand commun diviseur] Soit A un anneau commutatif quelconque
et soient deux éléments a, b ∈ A . On dit qu’un élément c ∈ A est un plus grand commun
diviseur entre a et b, ce qu’on note c = pgcd(a, b), lorsque :
• c divise a et c divise b ;
• si un élément d ∈ A divise simultanément a et b, alors en fait, d divise c
Classiquement, le fait qu’un élément p ∈ A divise un autre élément q ∈ A se note :
p | q.
Définition 4.4. [Plus petit commun multiple] Soit A un anneau quelconque et soient
deux éléments a, b ∈ A . On dit qu’un élément e ∈ A est un plus petit commun multiple
entre a et b, ce qu’on note e = ppcm(a, b), lorsque :
• a | e et b | e ;
• si un élément f ∈ A est divisible simultanément par a et par b, alors en fait, e | f .
Certes en général, pgcd et ppcm ne sont pas, strictement parlant, uniques. Toutefois, il
est aisé, sur A = Z et sur A = Z[x] d’assurer leur unicité (voir infra).
Comme on le sait, entre deux nombres quelconques a, b ∈ Z, le pgcd est unique dès lors
qu’on demande qu’il appartienne à N. Alors le lecteur-étudiant reconstituera sans difficulté
la démonstration des propriétés élémentaires du pgcd.
Lemme 4.5. Sur l’anneau Z des entiers naturels, la fonction à deux arguments pgcd(·, ·)
possède les cinq propriétés suivantes :
(i) pgcd(a, b) = |a| ⇐⇒ a | b ;
(ii) pgcd(a, b) = pgcd(b, a) ;
(iii) pgcd a, pgcd(b, c) = pgcd pgcd(a, b), c .
(iv) pgcd(c · a, c · b) = |c| pgcd(a, b).
(v) |a| = |b| =⇒ pgcd(a, c) = pgcd(b, c).
Notons « pour le fun » que l’associativité générale s’écrit :
pgcd(a1 , . . . , an ) = pgcd a1 , pgcd(a2 , . . . , pgcd(an−1 , an ) . . . ) .
Les anneaux euclidiens sont exactement ceux dans lesquels des divisions euclidiennes
successives sont possibles, notamment pour trouver un pgcd entre deux éléments quel-
conques donnés.
4. Anneaux intègres euclidiens 7
En partant de deux éléments a, b ∈ A que l’on renomme r0 , r1 ∈ A avec δ(r0 ) > δ(r1 ),
une première division euclidienne :
r0 = q1 r1 + r2 ,
suivie de divisions successives entre les restes nouveaux r2 , r3 , r4 , . . . qui appaissent, peut
être représentée synoptiquement comme suit :
δ(r0 ) > δ(r1 )
r0 = q1 r1 + r2
δ(r1 ) > δ(r2 )
r1 = q2 r2 + r3
δ(r2 ) > δ(r3 )
r2 = q3 r3 + r4
δ(r3 ) > δ(r4 )
r3 = q4 r4 + 0
où l’on suppose ici que le procédé termine à la quatrième division, à savoir que r5 = 0.
Lorsque A = Z, il est bien connu alors que le pgcd est le dernier reste non nul, ici r4 , et on
démontre en cours d’Algèbre que cela est encore vrai dans tout anneau euclidien (A , δ).
Algorithme: Division euclidienne classique
• Entrées : Deux éléments a, b ∈ (A , δ) d’un anneau commutatif intègre euclidien
A muni d’une fonction euclidienne δ.
• Sortie : Un plus grand commun diviseur h ∈ A entre a et b.
r0 ←−[ a, r1 ←−[ b.
i ←−[ 1
tant que ri 6= 0 faire ri+1 ←−[ Reste ri−1 divisé par ri
i ←−[ i + 1
Retourner ri−1 .
Comme cela a déjà été illustré sur l’exemple qui le précède, cet algorithme (antique)
divise les restes successifs :
δ(ri−1 ) > δ(ri )
ri−1 = qi ri + ri+1 ,
remplace à chaque étape les couples :
[ri , ri+1 ] ←−[ [ri−1 , ri ],
puis recommence à diviser :
δ(ri ) > δ(ri+1 )
ri = qi+1 ri+1 + ri+2 ,
8 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
et ainsi de suite.
Sans utiliser d’indices, l’algorithme de division euclidienne classique peut aussi être
représenté sous la forme d’une carte d’instructions en boucle :
Exemple 4.6. Il est avisé de représenter synoptiquement la recherche, déjà entamée supra,
du pgcd entre 126 et 35 :
126 > 35
126 = 3 · 35 + 21
35 > 21
35 = 1 · 21 + 14
21 > 14
21 = 1 · 14 + 7
14 > 7
14 = 2 · 7 + 0,
et ici, puisque le cinquième reste r5 = 0 est nul, l’avant-dernier reste r4 = 7 est un (le)
pgcd recherché.
Exemple 4.7. De manière alternative, on peut représenter sous forme d’un tableau le calcul
qui montre que 315 et 307 sont premiers entre eux.
5. Croissance des expressions intermédiaires et normalisations
Les calculs avec des polynômes, des fractions rationnelles, ou des matrices à coefficients
entiers souffrent souvent d’une « maladie » propre au calcul numérique ou symbolique : la
croissance parfois débridée des expressions.
5. Croissance des expressions intermédiaires et normalisations 9
Exemple 5.1. Voici le déroulement du calcul du plus grand commun diviseur entre les deux
polynômes à coefficients entiers :
A = 7 x5 − 22 x4 + 55 x3 + 94 x2 − 87 x + 56
=: R0 ,
B = 62 x4 − 97 x3 + 73 x2 + 4 x + 83
=: R1 ,
au moyen de l’algorithme d’Euclide ; à cause notamment du fait que les deux coefficients
de tête 7 et 62 de A et de B ne sont pas des unités, les polynômes-restes dans les divisions
successives :
R2 := reste dans la division de R0 par R1 ,
R3 := reste dans la division de R1 par R2 ,
R4 := reste dans la division de R2 par R3 ,
R5 := reste dans la division de R3 par R4 ,
possèdent des coefficients rationnels qui « explosent » de manière assez surprenante :
113293 3 409605 2 183855 272119
R2 = x + x − x+ ,
3844 3844 1922 3844
18423282923092 2 15239170790368 10966361258256
R3 = x − x+ ,
12835303849 12835303849 12835303849
216132274653792395448637 631179956389122192280133
R4 = − x− ,
44148979404824831944178 88297958809649663888356
20556791167692068695002336923491296504125
R5 = .
3639427682941980248860941972667354081
Afin de remédier — au moins en partie — à ce phénomène, il est avisé de normaliser
systématiquement les polynômes intermédiaires de manière à ce que le coefficient de leur
terme de tête soit toujours égal à 1.
Terminologie 5.2. Étant donné un polynôme de degré k > 0 :
P (x) = ck xk + ck−1 xk−1 + · · · + +c0 (ck 6= 0),
on appelle coefficient de tête le nombre :
ck ∈ A ,
et on dit que P unitaire lorsque :
ck = 1.
Par exemple, dans l’anneau A = Q[x] des polynômes à coefficients dans le corps des
nombres rationnels, on peut toujours diviser P (x) par son coefficient de tête de manière à
le rendre unitaire :
1 ck−1 k−1 c0
P (x) = xk + x + ··· + .
ck ck ck
Une expérience renouvelée des calculs à la main ou sur ordinateur a montré que dans l’al-
gorithme d’Euclide, il est avisé de rendre unitaires tous les restes intermédiaires afin de
rabaisser la complexité des coefficients rationnels des polynômes. Au final, après exécu-
tion de toutes les divisions euclidiennes requises, le polynôme pgcd entre deux polynômes
donnés A, B ∈ Q[x] :
pgcd(A, B) ∈ Q[x],
10 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
sera connu à un facteur rationnel non nul près.
Bien entendu, ce qui est vrai ici pour Q[x] est vrai aussi pour tout anneau de polynômes
K[x] à coefficients dans un corps commutatif K.
Mais comment s’y prendre si l’on désire travailler, plus généralement, avec l’anneau des
polynômes à coefficients dans un anneau euclidien A qui n’est pas forcément un corps ?
Il suffit — certes un peu artificiellement — de demander l’existence de formes nor-
males au sens précis qui suit.
Définition 5.3. Un anneau euclidien est dit normal si tout élément a ∈ A possède une
forme normale unique :
Normal(a) ∈ A
qui diffère de a simplement par une unité :
a = u · Normal(a) (u ∈ A × ),
la forme normale d’un produit quelconque entre deux éléments a, b ∈ A étant égale au
produit des formes normales :
Normal(a b) = Normal(a) Normal(b),
deux éléments a ∈ A et a0 ∈ A ayant la même forme normale :
Normal(a) = Normal(a0 )
lorsque, et seulement lorsque, ils diffèrent d’une unité :
a0 = u a (u ∈ A × ).
Il est avisé d’introduire une notation pour l’unité dont un élément a ∈ A et sa forme
normale diffèrent :
a
Unite(a) := .
Normal(a)
Dans un anneau euclidien normal, pgcd et ppcm entre deux éléments quelconques sont
alors définis de manière unique, simplement en prenant les formes normales.
Exercice 2. Justifer l’affirmation qui précède.
Exercice 3. (a) Sur A = Z, déterminer la forme normale naturelle d’un entier.
(b) Faire de même sur A = K[x], où K est un corps.
(c) En utilisant la normalisation de (a), traiter l’algorithme d’Euclide qui permet de calculer le pgcd entre
deux entiers relatifs quelconques a, b ∈ Z.
6. Algorithme d’Euclide étendu
Soit (A , δ) un anneau commutatif unitaire euclidien normal. L’idée pour raffiner l’al-
gorithme d’Euclide, simple et déjà comprise plus haut, consiste, lorsqu’on divise itérative-
ment, à normaliser les restes à chaque étape. En tout cas, sans remplacer les restes intermé-
diaires par leurs formes normales, en partant de deux éléments a, b ∈ A avec δ(b) 6 δ(a)
que l’on renomme :
r0 := a et r1 := b,
6. Algorithme d’Euclide étendu 11
rappelons que l’algorithme de divisions successives jusqu’à épuisement se représente
comme suit :
r0 = q1 r1 + r2 ,
r1 = q2 r2 + r3 ,
.. .. ..
. . .
ri−1 = qi ri + ri+1 ,
... ... ...
r`−2 = q`−1 r`−1 + r` ,
r`−1 = q` r` + 0,
le dernier reste non nul valant :
r` = pgcd(r0 , r1 ) = pgcd(a, b).
Maintenant, si l’on souhaite faire voir que les restes intermédiaires doivent être norma-
lisés, on les représentera sous la forme :
ρi ri avec ρi = Unite ρi ri ,
ri = Normal(ρi ri ),
et en supposant pour simplifier que l’on a déjà normalisé au départ :
r0 := Normal(a), ρ0 := Unite(a), a = ρ0 r0 ,
r1 := Normal(b), ρ1 := Unite(b), b = ρ 1 r1 ,
de telle sorte les nouveaux restes intermédiaires avec spécification de normalisation s’écri-
ront :
ρ2 r2 , ρ3 r3 , . . . . . . , ρ` r` ,
on obtiendra la représentation synoptique :
r0 = q1 r1 + ρ2 r2 ,
r1 = q2 r2 + ρ3 r3 ,
.. .. ..
. . .
ri−1 = qi ri + ρi+1 ri+1 ,
... ... ...
r`−2 = q`−1 r`−1 + ρ` r` ,
r`−1 = q` r` + 0.
De plus, il s’avère dans certaines applications arithmétiques du calcul de pgcd que tous
les résultats intermédiaires possèdent une utilité. Si donc l’on part de deux éléments quel-
conques a, b ∈ A d’un anneau euclidien normal A , une organisation systématique (voir
ce qui va suivre) des calculs donnera au final l’identité de Bézout :
s` a + t` b = pgcd(a, b),
mais à chaque étape intermédiaire, on devra aussi écrire :
si a + ti b = ri (0 6 i 6 `). (∗)
12 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
En fait, il est aisé d’expliquer comment construire par récurrence de tels éléments si , ti .
Pour i = 0 et pour i = 1, on a tout d’abord :
1
· a + 0 · b = r0 =: s0 a + t0 b,
ρ0
1
0·a+ · b = r1 =: s1 a + t1 b,
ρ1
ce qui donne sans difficulté des couples (s0 , t0 ) et (s1 , t1 ) qui conviennent.
En raisonnant par récurrence, supposons pour un certain entier i avec 1 6 i 6 ` − 1, on
ait déjà obtenu aux deux niveaux i et i − 1 :
si−1 a + ti−1 b = ri−1 ,
si a + ti b = ri .
Alors en partant de l’identité de division euclidienne dans laquelle naît le (i + 1)-ème reste
(normalisé) :
ri−1 = qi ri + ρi+1 ri+1 ,
en réécrivant cette identité et en y insérant les deux identités admises par récurrence :
ρi+1 ri+1 = ri−1 − qi ri
= si−1 a + ti−1 b − qi si a + ti b
= si−1 − qi si a + ti−1 − qi ti b,
d’où après division par l’unité ρi+1 :
si−1 − qi si ti−1 − qi ti
ri+1 = a+ b
ρi+1 ρi+1
=: si+1 a + ti+1 b,
ce qui donne les relations de récurrence :
si−1 − qi si ti−1 − ti si
si+1 := et ti+1 := .
ρi+1 ρi+1
Nous pouvons maintenant formuler l’énoncé des instructions avant de démontrer
qu’elles sont correctes.
Algorithme: Division euclidienne étendue avec mémorisations
• Entrées : Deux éléments a, b ∈ A d’un anneau euclidien normal.
• Sorties : Un entier d’arrêt ` ∈ N, une collection d’éléments ρi , ri , si , ti ∈ A pour
0 6 i 6 ` + 1, et des quotients qi ∈ A pour 0 6 i 6 `, calculés comme suit.
• Algorithme :
ρ0 ←−[ Unite(a), r0 ←−[ Normal(a), s0 ←−[ 1/ρ0 , t0 ←−[ 0.
ρ1 ←−[ Unite(b), r1 ←−[ Normal(b), s1 ←−[ 0, t1 ←−[ 1/ρ1 .
i ←−[ 1
tant que ri 6= 0 faire
qi ←−[ quotient ri−1 divisé par ri
ρi+1 ←−[ Unite Reste(ri−1 divisé par ri )
ri+1 ←−[ Normal Reste(ri−1 divisé par ri )
6. Algorithme d’Euclide étendu 13
si+1 ←−[ si−1 − qi s
i ρi+1
ti+1 ←−[ ti−1 − qi ti ρi+1
i ←−[ i + 1
` ←−[ i − 1
Retourner `, ρi , ri , si , ti pour 0 6 i 6 ` + 1, et qi pour 1 6 i 6 `
Démonstration. On commence donc par normaliser a et b en introduisant :
a
r0 := = Normal(a) = Normal(r0 ),
ρ0
b
r1 := = Normal(b) = Normal(r1 ).
ρ1
Comme cela vient d’être implicitement décrit dans la formulation de cet algorithme
d’Euclide étendu, les calculs fournissent les relations suivantes entre les quantités ri , si , ti :
ρ2 r2 = r0 − q1 r1 , ρ 2 s2 = s0 − q 1 s1 , ρ 2 t2 = t0 − q1 t1 ,
.. .. .. .. .. ..
. = . . = . . = .
ρi+1 ri+1 = ri−1 − qi ri , ρi+1 si+1 = si−1 − qi si , ρi+1 ti+1 = ti−1 − qi ti ,
.. .. .. .. .. ..
. = . . = . . = .
0 = r`−1 − q` r` , ρ`+1 s`+1 = s`−1 − q` s` , ρ`+1 t`+1 = t`−1 − q` t` ,
la première colonne ayant déjà été vue, tandis que la seconde et la troisième, en partant de :
1
s0 := ρ0
, t0 := 0,
1
s1 := 0, t1 := ρ1
,
définissent par induction les quantités :
s2 , . . . , s`+1 et t2 , . . . , t`+1 ,
dont la nature s’éclaircira dans un instant, cf. l’équation (∗) ci-dessus.
Sachant que les deux multiplicateurs de Bézout si et ti se transforment simultanément
à chaque étape de l’algorithme, il est naturel de raisonner en termes de matrices 2 × 2, et
plus précisément, il est naturel d’introduire la matrice :
1
s0 t0 ρ0
0
R0 := = ,
s1 t1 0 ρ11
accompagnée des ` matrices :
0 1
Qi := 1 qi
− ρi+1 (1 6 i 6 `),
ρi+1
et enfin, d’introduire aussi les ` produits de matrices :
Ri := Qi · · · Q1 R0 (1 6 i 6 `).
14 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
Lemme ∗. Pour tout entier intermédiaire i avec 0 6 i 6 `, on a :
a ri
Ri · = ,
b ri+1
et de plus, ces matrices Ri valent :
si ti
Ri = .
si+1 ti+1
avec la convention que ρ`+1 = 1 et que r`+1 = 0.
Démonstration. En effet, pour i = 0, on a tout d’abord bien :
a s0 t0 a
R0 · =
b s1 t1 b
1 a
ρ0
0 a ρ0 r0
= = = .
0 ρ11 b b
ρ1
r1
Après cela, en supposant par récurrence que l’on a déjà au niveau i :
a ri
Qi · · · Q1 R0 · = ,
b ri+1
il suffit de multiplier cette équation par la matrice Qi+1 pour atteindre le niveau i + 1 :
a ri
Qi+1 Qi · · · Q1 R0 · = Qi+1 ·
b ri+1
0 1 ri
= 1
− ρqi+1
ρi+2 i+2
ri+1
!
ri+1
= ri
ρi+2
− qi+1 ri+1
ρi+2
ri+1
= .
ri+2
Ensuite, si, à un certain niveau i avec 0 6 i 6 `, la matrice Ri possède bien l’expression
annoncée (ce qui est d’emblée le cas pour i = 0), alors au niveau i + 1, puisque :
Ri+1 = Qi+1 Ri ,
on déduit l’expression :
si ti 0 1 si ti
Qi+1 · = 1
− ρqi+1
si+1 ti+1 ρi+2 i+2
si+1 ti+1
si+1 ti+1
= si −qi+1 si+1 ti −qi+1 ti+1
ρi+2 ρi+2
si+1 ti+1
= ,
si+2 ti+2
ce qui termine la démonstration.
6. Algorithme d’Euclide étendu 15
L’égalité matricielle de ce lemme s’écrit donc :
si ti a ri
= ,
si+1 ti+1 b ri+1
et elle donne, pour tout 0 6 i 6 ` + 1, les identités de Bézout intermédiaires :
si a + ti b = ri .
Au niveau i = ` + 1, puisque le dernier reste r`+1 = 0 est nul, on a donc :
s`+1 a + t`+1 b = 0,
et au niveau i = ` juste avant, on a l’identité de Bézout :
s` a + t` b = r` .
puis que nous pouvons maintenant démontrer effectivement que :
r` = pgcd(a, b).
Lemme ∗. Avec les mêmes notations, toujours pour i = 0, 1, . . . , `, les cinq propriétés
suivantes sont satifaites :
(i) pgcd(a, b) = pgcd(ri , ri+1 ) = r` ;
(−1)i
(ii) si ti+1 − ti si+1 = ρ0 ···ρi+1
, et pgcd(si , ti ) = 1 ;
(iii) pgcd(ri , ti ) = pgcd(a, ti ) ;
(iv)
a = (−1)i ρ0 · · · ρi+1 ti+1 ri − ti ri+1 ,
b = (−1)i+1 ρ0 · · · ρi+1 si+1 ri − si ri+1 .
Démonstration. Pour (i), soit i ∈ {0, . . . , `}. Grâce au lemme qui précède vu au niveau `,
on a :
r` a a
= R` = Q` · · · Qi+1 Ri
0 b b
ri
= Q` · · · Qi+1 .
ri+1
Cette identité montre que r` est une combinaison linéaire de ri et de ri+1 , donc le pgcd
normalisé entre ri et ri+1 divise r` .
D’un autre côté, puisque le déterminant :
1
det Qi = − ρi+1
est une unité dans A , la matrice Qi est inversible, d’inverse :
−1 qi ρi+1
Qi =
1 0
ce qui nous permet d’inverser aisément l’identité que nous venons d’obtenir :
ri −1 −1 r`
= Qi+1 · · · Q` .
ri+1 0
Ceci montre que ri et ri+1 sont tous les deux divisibles par r` .
16 François DE M ARÇAY, Département de Mathématiques d’Orsay, Université Paris-Saclay, France
Enfin, puisque r` est normal, et puisque le pgcd est défini de manière unique en passant
à la forme normale, il en découle que :
r` = pgcd(ri , ri+1 ),
ce qui, au niveau i = 0, donne :
pgcd(a, b) = pgcd(r0 , r1 ) = r` .
Ensuite, (ii) se vérifie en calculant des produits de déterminants :
si ti s0 t0
si ti+1 − ti si+1 = det = det Ri = det Qi · · · det Q1 det
si+1 ti+1 s1 t1
(−1)i
= ,
ρi+1 · · · ρ2 ρ1 ρ0
ce qui implique (exercice mental) que :
pgcd(si , ti ) = 1 .
Maintenant pour (iii), observons que les deux pgcd incorporent ti . Pour montrer qu’il
sont égaux, il suffit donc (exercice mental) de faire voir que pour tout diviseur d de ti :
d | a ⇐⇒ d | ri .
Soit donc d un diviseur quelconque de ti .
Si d | a, alors aussi d divise si a + ti b = ri .
Inversement, si d divise ri , alors aussi d divise ri −ti b = si a. Mais comme pgcd(si , ti ) =
1, tout diviseur d de ti est premier avec si , et donc si d divise si a, c’est que d doit diviser a.
Pour (iv), puisque qu’il découle de (ii) (exercice visuel) que la matrice Ri est inversible
d’inverse :
−1 i ti+1 − ti
Ri = (−1) ρ0 · · · ρi+1
− si+1 si
on peut récrire l’identité du lemme qui précède sous la forme :
a −1 ri
= Ri
b ri+1
i ti+1 − ti ri
= (−1) ρ0 · · · ρi+1
− si+1 si ri+1
i ti+1 ri − ti ri+1
= (−1) ρ0 · · · ρi+1
− si+1 ri+1 + si ri+1
ce qui conclut la démonstration
L’explication démonstrative de l’Algorithme de division euclidienne étendue est ache-
vée.
