L’algorithme d’Euclide permet de calculer le PGCD de deux entiers naturels non nuls $a$ et $b$.
On procède de la manière suivante :
-
On effectue la division euclidienne de $a$ par $b$. On note $r$ le reste (on n’utilise pas le quotient).
-
On remplace ensuite $a$ par $b$ et $b$ par $r$.
-
Tant que le reste est différent de 0, on réitère le procédé.
Après un certain nombre d’itérations, on obtiendra un reste égal à 0.
Le PGCD de $a$ et de $b$ est alors le reste précédent (c’est à dire le dernier reste non nul).
Exemple
Calculons le PGCD de 216 et de 126 à l’aide de l’algorithme d’Euclide (le tableau ci-dessous peut être obtenu avec l’outil Outil : Algorithme d’Euclide)
| N° Ligne |
Dividende ($a$) |
Diviseur ($b$) |
Quotient |
Reste ($r$) |
| 1 |
216 |
126 |
1 |
90 |
| 2 |
126 |
90 |
1 |
36 |
| 3 |
90 |
36 |
2 |
18 |
| 4 |
36 |
18 |
2 |
0 |
Ligne 1 : On effectue la division euclidienne de 216 par 126. Le quotient est 1 et le reste 90.
Ligne 2 : Dans la colonne « Dividende ($a$) », on place le diviseur de la ligne précédente soit 126.
Dans la colonne « Diviseur ($b$) », on place le reste de la ligne précédente soit 90.
On effectue alors la division euclidienne de 126 par 90. Le quotient est 1 et le reste 36.
Ligne 3 : Le reste précédent est non nul donc on recommence l’opération.
Dans la colonne « Dividende ($a$) », on place le diviseur de la ligne précédente soit 90.
Dans la colonne « Diviseur ($b$) », on place le reste de la ligne précédente soit 36.
On effectue alors la division euclidienne de 90 par 36. Le quotient est 2 et le reste 18.
Ligne 4 : Le reste précédent est là encore différent de zéro.
On recommence donc une nouvelle fois l’opération.
Dans la colonne « Dividende ($a$) », on place le diviseur de la ligne précédente soit 36.
Dans la colonne « Diviseur ($b$) », on place le reste de la ligne précédente soit 18.
On effectue alors la division euclidienne de 36 par 18. Le quotient est 2 et le reste 0.
Cette fois ci, le reste est nul. On a donc terminé le calcul.
Le PGCD est le dernier entier différent de zéro dans la colonne des restes. C’est donc 18.
