Calcul du PGCD – Algorithme d’Euclide
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.
PGCD(216 , 126) = 18