09/08/2019 Mathraining | Algorithme d'Euclide
Algorithme d'Euclide
Prérequis
Divisibilité et nombres premiers
Résumé
Les notions de plus grand commun diviseur (PGCD) et plus petit commun multiple (PPCM) sont
fondamentales en théorie des nombres, et ce chapitre commence par leur définition. Nous présentons
ensuite l'algorithme d'Euclide permettant justement de calculer le PGCD de deux nombres entiers, aussi
grands soient-ils. Outre cette possibilité, cet algorithme est également très utile d'un point de vue
théorique. En effet, il nous permettra notamment par la suite de démontrer le théorème de Bézout et de
calculer l'inverse d'un nombre en arithmétique modulaire.
1. PGCD et PPCM
Définitions
Rappelons les définitions des PGCD et PPCM.
Définition
Le plus grand commun diviseur (PGCD) de deux nombres naturels x et y, que nous noterons (x, y)
(ou parfois pgcd(x, y) pour être plus explicite), est comme son nom l'indique le plus grand nombre
entier divisant x et y à la fois.
Par exemple, on a (15, 20) = 5 .
Définition
Le plus petit commun multiple (PPCM) de deux nombres naturels x et y, parfois noté [x, y] ou
ppcm(x, y) , est le plus petit nombre entier strictement positif multiple de x et de y à la fois.
On a par exemple [15, 20] = 60 .
Remarque : Ces deux notions ne sont pas bien définies lorsque les deux nombres sont nuls. On
supposera donc toujours être dans le cas où l'un des deux nombres est différent de 0. Par contre, elles
ont tout à fait un sens lorsqu'un seul des deux nombres est nuls. Dans ce cas, on a (a, 0) = a et
[a, 0] = 0 car tous les entiers non-nuls divisent 0 et 0 ne divise aucun entier non-nul.
Calcul
https://www.mathraining.be/chapters/1?type=10 1/4
09/08/2019 Mathraining | Algorithme d'Euclide
Si les décompositions en facteurs premiers de x et de y sont connues, alors il est aisé de calculer leur
PGCD et PPCM. En effet, notons
e1 e2 en
x = p ⋅ p ⋅ … ⋅ pn ,
1 2
f f f
1 2 m
y = q ⋅ q ⋅ … ⋅ qm
1 2
les décompositions des deux nombres. Quitte à rajouter des termes avec exposant 0 (rappelons que
x = 1 par convention si x ≠ 0 ), nous pouvons supposer que les pi et qi apparaissant dans les deux
0
décompositions sont les mêmes (par exemple, au lieu d'écrire 15 et 20 , on peut
1 1 2 1
= 3 ⋅ 5 = 2 ⋅ 5
écrire 15 = 20 ⋅ 31 ⋅ 51 et 20 = 22 ⋅ 30 ⋅ 51 ) :
e1 e2 en
x = p ⋅ p ⋅ … ⋅ pn ,
1 2
f f f
1 2 n
y = p ⋅ p ⋅ … ⋅ pn .
1 2
De là, nous pouvons déduire la décomposition en facteurs premiers de (x, y) et [x, y]. En effet, (x, y)
doit tout d'abord diviser les deux nombres x et y, donc ses facteurs premiers doivent forcément être des
éléments pi . Et à chaque facteur pi , vu que nous cherchons le plus grand diviseur, il est optimal de
mettre le plus grand exposant possible. Pour continuer à diviser x et y, l'exposant à mettre est
min(ei , fi ) . Ainsi, on en déduit
min(e 1 ,f ) min(e 2 ,f ) min(e n,f )
1 2 n
(x, y) = p ⋅ p ⋅ … ⋅ pn .
1 2
De la même façon, on trouve que
max(e 1 ,f ) max(e 2 ,f ) max(e n,f )
1 2 n
[x, y] = p ⋅ p ⋅ … ⋅ pn .
1 2
Ainsi, pour notre exemple, on retrouve bien
min(0,2) min(1,0) min(1,1) 0 0 1
(15, 20) = 2 ⋅ 3 ⋅ 5 = 2 ⋅ 3 ⋅ 5 = 5,
max(0,2) max(1,0) max(1,1) 2 1 1
[15, 20] = 2 ⋅ 3 ⋅ 5 = 2 ⋅ 3 ⋅ 5 = 60.
Première propriété
Cette constatation nous permet de démontrer le résultat suivant :
Propriété
Si x, y ∈ N0 , on a toujours
(x, y) ⋅ [x, y] = x ⋅ y.
Démonstration
Si on regarde un seul facteur premier p de la décomposition, il apparaît avec l'exposant min(e, f )
dans (x, y) et avec l'exposant max(e, f ) dans [x, y]. Dans le membre de gauche de l'égalité, son
https://www.mathraining.be/chapters/1?type=10 2/4
09/08/2019 Mathraining | Algorithme d'Euclide
exposant sera donc min(e, f ) + max(e, f ) . Dans le membre de droite, son exposant sera e + f , et
la conclusion découle du fait que
min(e, f ) + max(e, f ) = e + f .
Sur notre exemple, remarquons que l'on a bien
(15, 20) ⋅ [15, 20] = 5 ⋅ 60 = 300 = 15 ⋅ 20.
Difficulté
Malheureusement, on ne connaît pas toujours la décomposition en facteurs premiers des nombres qui
nous intéressent. Nous allons cependant voir qu'il existe un moyen très efficace pour calculer le PGCD de
deux nombres : l'algorithme d'Euclide. De plus, au vu de la formule précédente reliant le PGCD et le
PPCM, on sera également en mesure de calculer le PPCM de deux nombres.
2. Algorithme d'Euclide
Idée première
Derrière l'algorithme d'Euclide se cache une propriété simple :
(a, b) = (a − b, b) si a ≥ b ≥ 0 (a, b )
∈ N .
Cette égalité découle du fait que l'ensemble des diviseurs communs de a et b est le même que
l'ensemble des diviseurs communs de a − b et b. En effet, tout élément divisant a et b divise également
a − b , et inversement, tout élément divisant a − b et b divise également a .
De là, il est évident que le plus grand commun diviseur de a et b est égal au plus grand commun diviseur
de a − b et b.
En appliquant cette égalité k fois à la suite, on a même
(a, b) = (a − k ⋅ b, b) tant que a − k ⋅ b ≥ 0.
L'algorithme
Lorsque l'on désire calculer le PGCD de deux nombres a et b, on peut donc remplacer a par a − k ⋅ b ,
un nombre plus petit. Autant prendre k le plus grand possible, à savoir le quotient q de la division
euclidienne de a par b. Remplacer a par a − q ⋅ b revient donc à remplacer a par le reste de la division
euclidienne de a par b.
L'algorithme d'Eucide consiste à appliquer cette opération plusieurs fois de suite jusqu'à ce que l'un des
deux nombres soit égal à 0. Puisque rien ne vaut un bon exemple, calculons (78, 33) à l'aide de cet
algorithme :
https://www.mathraining.be/chapters/1?type=10 3/4
09/08/2019 Mathraining | Algorithme d'Euclide
(78, 33) = (78 − 2 ⋅ 33, 33) = (12, 33)
(33, 12) = (33 − 2 ⋅ 12, 12) = (9, 12)
(12, 9) = (12 − 1 ⋅ 9, 9) = (3, 9)
(9, 3) = (9 − 3 ⋅ 3, 3) = (0, 3) = 3
Une façon plus courante et plus pratique d'écrire cet algorithme est d'écrire les divisions euclidiennes
successives :
78 = 2 ⋅ 33 + 12
33 = 2 ⋅ 12 + 9
12 = 1 ⋅ 9 + 3
9 = 3 ⋅ 3 + 0
On constate qu'il suffit d'effectuer la division euclidienne de a par b (ici 78 et 33 ), puis de recommencer
en remplacant a par b (33 ) et b par le reste obtenu (12 ). On effectue ainsi une succession de divisions
euclidiennes, et le PGCD est finalement donné par le dernier reste non-nul trouvé (3 sur notre exemple).
En toute généralité, on écrit
a = q0 ⋅ b + r 0
b = q1 ⋅ r 0 + r 1
r 0 = q2 ⋅ r 1 + r 2
r n−2 = qn ⋅ r n−1 + rn
r n−1 = qn+1 ⋅ r n + 0
Remarquons à nouveau qu'en calculant ainsi le PGCD des nombres a et b, on a également calculé leur
PPCM puisque l'on a vu précédemment que
a. b
[a, b] = .
(a, b)
Dans notre exemple, on a directement que
78 ⋅ 33
[78, 33] = = 858.
3
Importance
En plus d'être très efficace d'un point de vue calculatoire (il est couramment utilisé en informatique), cet
algorithme est très utile d'un point de vue théorique. C'est grâce à lui que nous allons démontrer sans
peine le théorème de Bézout, résultat phare d'un prochain chapitre.
Marquer toute la théorie comme lue
Des questions ? N'hésitez pas à demander de l'aide sur le forum !
https://www.mathraining.be/chapters/1?type=10 4/4
