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)

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