Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Calcul du PGCD - Algorithme d'Euclide

L'algorithme d'Euclide permet de calculer le PGCD de deux entiers naturels non nuls aa et bb.

On procède de la manière suivante :

Après un certain nombre d'itérations, on obtiendra un reste égal à 0.

Le PGCD de aa et de bb 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 (aa) Diviseur (bb) Quotient Reste (rr)
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 (aa)", on place le diviseur de la ligne précédente soit 126.

Dans la colonne "Diviseur (bb)", 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 (aa)", on place le diviseur de la ligne précédente soit 90.

Dans la colonne "Diviseur (bb)", 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 (aa)", on place le diviseur de la ligne précédente soit 36.

Dans la colonne "Diviseur (bb)", 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