Comment calculer un PGCD avec l’algorithme d’Euclide ?

Réponse courte

Divise le plus grand entier par le plus petit, puis remplace le couple par le diviseur et le reste. Répète jusqu’au reste nul : le dernier reste non nul est le PGCD.

Comprendre

L’idée de l’algorithme

Pour deux entiers positifs a≥b, la division euclidienne donne a=bq+r avec 0≤r<b. Les diviseurs communs de a et b sont exactement ceux de b et r. On peut donc remplacer le couple sans modifier son PGCD, jusqu’à atteindre un reste nul.

Calcul pas à pas

Cherchons PGCD(252,105) : 252=2×105+42 ; 105=2×42+21 ; 42=2×21+0. Le dernier reste non nul est 21, donc PGCD(252,105)=21. Contrôle : 252=12×21 et 105=5×21.

Autre exemple

Pour 84 et 30 : 84=2×30+24 ; 30=1×24+6 ; 24=4×6+0. Le PGCD vaut 6. Les restes diminuent strictement, donc la procédure finit.

Pièges fréquents

Le PGCD est le dernier reste non nul, pas le dernier reste (qui vaut toujours zéro). Et chaque étape doit être une division euclidienne avec un reste plus petit que le diviseur ; une égalité approchée ne convient pas.

Étapes

  1. Range les deux entiers du plus grand au plus petit.
  2. Effectue la division euclidienne et note le reste.
  3. Remplace le couple par le diviseur et le reste.
  4. Arrête quand le reste vaut zéro ; retiens le reste non nul précédent.

Exemples

  • 252=2×105+42, 105=2×42+21, 42=2×21 : PGCD=21.
  • 84=2×30+24, 30=1×24+6, 24=4×6 : PGCD=6.

Pièges fréquents

  • Donner zéro comme PGCD parce que la dernière division a un reste nul : on retient le reste non nul qui le précède.
  • Ne pas remplacer le couple par diviseur-reste : cela empêche la chaîne de divisions de poursuivre correctement.

Pourquoi ça marche

L’égalité a=bq+r montre qu’un diviseur commun de a et b divise aussi r, et réciproquement.

Et maintenant ?

Questions proches

← Toutes les questions-réponses