Calcul du PGCD - Algorithme d'Euclide
L'algorithme d'Euclide permet de calculer le PGCD de deux entiers naturels non nuls et .
On procède de la manière suivante :
On effectue la division euclidienne de par . On note le reste (on n'utilise pas le quotient).
On remplace ensuite par et par .
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 et de 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 () | Diviseur () | Quotient | Reste () |
| 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 ()", on place le diviseur de la ligne précédente soit 126.
Dans la colonne "Diviseur ()", 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 ()", on place le diviseur de la ligne précédente soit 90.
Dans la colonne "Diviseur ()", 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 ()", on place le diviseur de la ligne précédente soit 36.
Dans la colonne "Diviseur ()", 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.
PGCD(216 , 126) = 18