PGCD et algorithme d'Euclide : fiche de Terminale (maths expertes)
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
Le PGCD de deux entiers est le plus grand entier qui les divise tous les deux 3.
Clé de l'algorithme : PGCD(a,b)=PGCD(b,r) où r est le reste de la division euclidienne de a par b, et PGCD(a,0)=a3.
On répète les divisions jusqu'à un reste nul ; le dernier reste non nul est le PGCD 3.
L'algorithme s'arrête toujours, car les restes diminuent strictement 3.
La version étendue fournit aussi des coefficients de Bézout u et v tels que au+bv=PGCD(a,b)4.
Ce qu'il faut savoir
La méthode pas à pas
Pourquoi ça s'arrête et pourquoi c'est juste
Aller plus loin : les coefficients de Bézout
Pièges fréquents
Questions flash
5 questions · correction immédiate · ton score reste sur ton appareil.
L'algorithme s'arrête dès qu'un reste est nul et renvoie le dernier reste non nul 3. Le reste nul final est seulement le signal d'arrêt, et les quotients ne servent qu'à écrire les divisions.
C'est la propriété centrale de l'algorithme 3. Les couples (a,b) et (b,r) ont les mêmes diviseurs communs ; la tentation de croire que le PGCD change à chaque étape est donc fausse.
On a 252=198×1+54, puis 198=54×3+36, puis 54=36×1+18, puis 36=18×2+0. Le dernier reste non nul est 18. Répondre 36 vient d'une erreur : 36 est un reste intermédiaire, pas le dernier non nul.
Le nouveau couple est (15,6) : l'ancien diviseur devient dividende et l'ancien reste devient diviseur. La première réponse garde le dividende de départ, ce qui ne suit pas l'algorithme.
L'algorithme d'Euclide étendu fournit un tel couple (u,v)4. Pour 21 et 15, 21×(−2)+15×3=3. Les coefficients peuvent être négatifs, ce qui ne contredit pas la définition.
Les questions qu'on se pose
Faut-il toujours mettre le plus grand nombre en premier ?
Ce n'est pas obligatoire. Si tu commences par le plus petit, la première division donne un quotient nul et un reste égal au petit nombre : les deux nombres se retrouvent dans l'ordre à l'étape suivante, car on remplace le plus grand par le reste 3. Mettre le plus grand en premier évite simplement une ligne.
Pourquoi utiliser l'algorithme d'Euclide plutôt que lister les diviseurs ?
Lister tous les diviseurs devient long dès que les nombres sont grands. L'algorithme d'Euclide calcule le PGCD efficacement 3 avec quelques divisions seulement, sans décomposer les nombres.
Comment sait-on que l'algorithme ne tourne pas indéfiniment ?
À chaque étape, le nouveau reste est positif et strictement plus petit que le diviseur 3. Une suite d'entiers positifs strictement décroissante ne peut pas durer toujours : elle atteint 0, et l'algorithme s'arrête.