Algorithme d’Euclide : calculer le PGCD facilement

L’algorithme d’Euclide est une méthode qui permet de trouver le PGCD de deux entiers grâce à des divisions euclidiennes successives. On s’arrête quand le reste vaut 0, et le dernier reste non nul est le PGCD.

Pourquoi 84 et 126 “se simplifient-ils bien” dans une fraction, alors que d’autres nombres semblent plus compliqués ? En classe, c’est souvent à ce moment-là que l’algorithme d’Euclide devient vraiment utile. J’aime cette méthode parce qu’elle évite de lister tous les diviseurs un par un, ce qui devient vite long. Avec quelques divisions euclidiennes bien posées, on trouve le PGCD de façon claire, rapide et rassurante. Pour un élève de collège, c’est une technique précieuse pour simplifier des fractions, résoudre des problèmes de partage et mieux comprendre le lien entre quotient et reste.

Qu’est-ce que l’algorithme d’Euclide ?

L’algorithme d'Euclide est une méthode qui permet de calculer rapidement le PGCD de deux entiers. On enchaîne des divisions euclidiennes jusqu’à obtenir un reste nul. Le dernier reste non nul est alors le PGCD recherché, c’est-à-dire le plus grand nombre qui divise exactement les deux nombres de départ.

Au collège, cette idée sert à répondre à des questions très concrètes. Le PGCD, ou plus grand commun diviseur, est le plus grand entier qui partage deux nombres sans laisser de reste. Il intervient dans la simplification des fractions, mais aussi dans des problèmes de partage en parts égales, de rangement par paquets identiques ou de découpage sans perte. L’algorithme d'Euclide porte le nom de Euclide, mathématicien de l’Antiquité grecque, dont les travaux ont marqué durablement la géométrie et l’arithmétique. Historiquement, la méthode existe sous une forme ancienne par soustractions successives : on retranche le plus petit nombre du plus grand jusqu’à faire apparaître une situation simple. Cette version aide à comprendre le principe, néanmoins elle devient vite longue. En 3e, on utilise surtout la version moderne par division euclidienne, plus directe et mieux adaptée aux exercices scolaires.

Pour bien suivre, il faut maîtriser quatre mots de vocabulaire. Dans une division euclidienne, le dividende est le nombre que l’on partage, le diviseur est celui par lequel on divise, le quotient indique combien de fois on peut prendre le diviseur, et le reste est ce qu’il reste à la fin. Par exemple, si l’on écrit 47 = 6 × 7 + 5, alors 47 est le dividende, 6 le diviseur, 7 le quotient et 5 le reste. L’idée clé de la méthode est fine mais très puissante : le pgcd de deux nombres ne change pas si l’on remplace le plus grand par le reste de sa division par le plus petit. Par conséquent, on recommence avec des nombres de plus en plus petits, ce qui fait avancer le calcul sans se perdre dans une longue liste de diviseurs.

C’est justement ce qui rend cette méthode si efficace. Chercher tous les diviseurs communs fonctionne pour de petits nombres, en revanche cela devient fastidieux dès que les valeurs grandissent. La décomposition en facteurs premiers est aussi très utile, mais elle demande parfois plus de travail intermédiaire. L’algorithme d'Euclide, lui, va droit au but et explique pourquoi il apparaît si souvent en 3e, notamment pour simplifier une fraction comme 84/126 ou résoudre un problème de partage maximal. Plus tard, on peut découvrir d’autres formulations : une version itérative, une version récursive, l’algorithme d’Euclide étendu qui relie le PGCD à l’identité de Bézout, ou encore des questions de démonstration et de rapidité de calcul, étudiées avec la complexité et le théorème de Lamé. Ces prolongements enrichissent la culture mathématique, sans changer le cœur de la méthode vue au collège.

Comment utiliser l’algorithme d’Euclide pour calculer le PGCD ?

Pour utiliser l’algorithme d’Euclide, on effectue une division euclidienne du plus grand nombre par le plus petit, puis on recommence avec le diviseur et le reste. Quand on obtient un reste nul, le dernier reste non nul est le PGCD des deux nombres. Cette méthode d’arithmétique est rapide, sûre et très pratique au collège.

Voici la méthode, écrite proprement et sans sauter d’étape, pour comprendre comment utiliser l’algorithme d’Euclide et calculer le PGCD sans se tromper : 1. On repère le plus grand des deux nombres. 2. On pose une division euclidienne : dividende = diviseur × quotient + reste. 3. On garde le diviseur et le reste, parce que le PGCD ne change pas quand on remplace le couple initial par diviseur, reste. 4. On recommence la division avec ce nouveau couple. 5. Quand le reste devient 0, on s’arrête : le dernier reste non nul donne le PGCD. La règle centrale est toujours la même : on ne repart jamais avec le quotient, seulement avec le diviseur et le reste. C’est là que beaucoup d’élèves confondent les rôles des nombres.

Prenons l’exemple complet de 84 et 30. On écrit d’abord : 84 = 30 × 2 + 24. Puis on remplace le couple (84 ; 30) par (30 ; 24). On continue : 30 = 24 × 1 + 6. On remplace alors par (24 ; 6). Nouvelle division : 24 = 6 × 4 + 0. Le reste nul apparaît, donc on s’arrête. Le dernier reste non nul est 6, donc PGCD(84 ; 30) = 6. Pour vérifier, on contrôle que 6 divise 84 et 6 divise 30. C’est exact : 84 ÷ 6 = 14 et 30 ÷ 6 = 5. On a donc bien réussi à calculer le PGCD. Cette vérification est utile, surtout quand une division a été mal posée ou qu’un reste a été recopié trop vite.

Mini-exemple avec 24 et 36, très fréquent en exercice. On commence par le plus grand : 36 = 24 × 1 + 12. Puis : 24 = 12 × 2 + 0. Le PGCD vaut donc 12. Ce résultat sert ensuite à simplifier une fraction : 24/36 = 2/3, car on divise le numérateur et le dénominateur par 12 pour obtenir une fraction irréductible. En revanche, dans un problème de partage, le PGCD donne la plus grande taille possible des groupes identiques : avec 84 et 30, on peut faire des lots de 6 sans reste. Les erreurs fréquentes sont connues : s’arrêter trop tôt, prendre le quotient à la place du reste, ou oublier que la bonne réponse est le dernier reste non nul, pas le dernier nombre écrit.

Exemple rédigé pas à pas avec 84 et 30

Pour calculer le PGCD de 84 et 30, on applique l’algorithme d’Euclide avec des divisions euclidiennes successives : 84 = 30 × 2 + 24, puis 30 = 24 × 1 + 6, enfin 24 = 6 × 4 + 0. Dès que le reste vaut 0, le dernier reste non nul est le PGCD : ici, c’est 6.

Comment lire ces calculs ? On divise toujours le plus grand nombre par le plus petit, puis on recommence avec le diviseur et le reste. Ainsi, 84 divisé par 30 donne un quotient de 2 et un reste de 24. Ensuite, 30 divisé par 24 donne un reste de 6. Enfin, 24 est divisible par 6, donc le reste devient 0 : la recherche s’arrête. En revanche, une erreur fréquente consiste à s’arrêter trop tôt, dès qu’on voit un reste “petit”. Or seul le dernier reste non nul compte. Par conséquent, le PGCD de 84 et 30 est 6. Application immédiate : pour simplifier la fraction 84/30, on divise le numérateur et le dénominateur par 6, ce qui donne 14/5. Cette fraction est alors irréductible.

Pourquoi l’algorithme d’Euclide fonctionne et pourquoi il s’arrête

L’algorithme d’Euclide fonctionne parce que le PGCD ne change pas si l’on remplace le plus grand nombre par le reste de sa division euclidienne par l’autre. Il s’arrête forcément, car les restes obtenus sont des entiers naturels toujours plus petits, donc cette suite décroissante finit par atteindre 0.

La clé de la démonstration est simple à comprendre au collège. Si a = bq + r, alors tout nombre qui divise à la fois a et b divise aussi r, puisque r = a - bq. Autrement dit, les diviseurs communs de a et b sont aussi des diviseurs communs de b et r. La réciproque est vraie également : si un nombre divise b et r, alors il divise a = bq + r. Par conséquent, les deux couples ont exactement les mêmes diviseurs communs, donc le même PGCD. Voilà pourquoi la méthode est correcte. Cette idée répond à la question pourquoi l’algorithme d’Euclide s’arrête seulement en partie ; elle explique d’abord pourquoi chaque étape conserve le bon résultat.

Prenons un exemple numérique. On cherche le PGCD de 84 et 30. On calcule 84 = 30 × 2 + 24. Le PGCD de 84 et 30 est donc le même que celui de 30 et 24. Puis 30 = 24 × 1 + 6, donc ce PGCD est aussi celui de 24 et 6. Enfin, 24 = 6 × 4 + 0. On s’arrête, et le dernier reste non nul est 6. Cette rédaction est déjà une petite démonstration algorithme d'euclide, car elle montre à chaque ligne que l’on garde les mêmes diviseurs communs. En revanche, il ne faut pas confondre le quotient et le reste : seul le reste sert à poursuivre l’algorithme. C’est l’erreur classique chez les élèves.

Pourquoi l’algorithme finit-il toujours ? À chaque division euclidienne, le reste est compris entre 0 et le diviseur, sans jamais l’atteindre. Donc les restes diminuent strictement : on passe, par exemple, de 30 à 24 puis de 24 à 6 puis à 0. Or on travaille dans les entiers naturels ; une suite strictement décroissante ne peut pas descendre sans fin. Elle atteint nécessairement 0, ce qui clôt le calcul. Au lycée, cette idée est formulée plus rigoureusement, avec une preuve générale. Des mathématiciens ont aussi étudié la rapidité de la méthode : le théorème de Lamé la relie aux nombres de Fibonacci. Pour la culture générale, on peut signaler des explications géométriques anciennes, ainsi que l’algorithme original par différences successives, plus intuitif mais souvent moins rapide.

Exercices corrigés, erreurs fréquentes et ouvertures utiles

Pour réussir un exercice sur l’algorithme d’Euclide, il faut poser correctement chaque division, garder les restes dans le bon ordre et conclure avec le dernier reste non nul. Cette méthode sert à trouver un PGCD, à simplifier une fraction et à résoudre des problèmes concrets de partage ou de découpage.

Voici des exercices corrigés typiques de collège. Pour calculer le PGCD de 252 et 198, on écrit 252 = 198 × 1 + 54, puis 198 = 54 × 3 + 36, puis 54 = 36 × 1 + 18, puis 36 = 18 × 2 + 0. Le PGCD vaut donc 18. Pour simplifier la fraction 252/198, on divise le numérateur et le dénominateur par 18 : on obtient 14/11. Pour un problème de découpage, imagine 252 cm et 198 cm de ruban à couper en morceaux de même longueur, sans reste. La plus grande longueur possible est encore 18 cm. Le raisonnement reste le même. On cherche toujours le plus grand nombre qui partage les deux mesures exactement.

Les erreurs fréquentes sont faciles à repérer. La plus classique consiste à annoncer comme réponse le dernier quotient au lieu du dernier reste non nul. Autre piège : inverser dividende et diviseur dans une ligne, ce qui casse toute la chaîne. Certains élèves s’arrêtent trop tôt, dès qu’ils voient un petit reste. Il faut continuer jusqu’à obtenir 0. Pour éviter ces fautes, je conseille de présenter les divisions sur des lignes séparées, avec les restes bien alignés. Relire chaque égalité aide beaucoup. Si le PGCD trouvé ne divise pas les deux nombres, il y a une erreur de calcul. Ce contrôle final prend dix secondes et sauve souvent l’exercice.

La méthode du collège ouvre déjà vers des idées plus avancées. L’algorithme d'euclide étendu permet d’écrire le PGCD sous la forme donnée par le théorème de Bézout : ax + by = pgcd(a, b). On le rencontre plus tard en spécialité, en licence, ou en informatique. On peut aussi programmer un algorithme d'euclide python ou en C avec quelques lignes seulement, ou pour apprendre à calculer une racine. Pour les curieux, il existe même une version algorithme d'euclide polynome dans K[X]. Des ressources PDF sérieuses sont proposées par le Laboratoire de Mathématiques d'Orsay, Bibm@th, Unisciel ou l’Université de Montréal. Ces prolongements montrent qu’une technique simple de collège appartient à une grande famille d’idées mathématiques.

Les erreurs les plus fréquentes en 3e

Les erreurs classiques sont presque toujours les mêmes : on inverse les nombres dans la division euclidienne, on oublie un reste, on croit que le PGCD est le quotient, ou bien on s’arrête trop tôt. La bonne règle est simple : le PGCD est le dernier reste non nul. Vérifiez chaque ligne. Le reste doit toujours être plus petit que le diviseur.

En 3e, la confusion la plus fréquente consiste à faire la division dans le mauvais ordre : on doit toujours diviser le plus grand nombre par le plus petit. Sinon, la suite des calculs se dérègle. Autre piège : oublier d’écrire un reste, surtout quand il vaut 0 ; pourtant, c’est justement ce zéro qui indique l’arrêt. Certains élèves concluent avec le quotient, alors qu’il ne sert pas à donner le PGCD. Enfin, l’arrêt prématuré est courant : si le reste n’est pas nul, on continue. Astuce simple : relisez la dernière ligne ; si vous voyez un reste non nul, l’algorithme n’est pas fini, et si vous voyez 0, le PGCD est le reste précédent.

Comment calculer le PGCD 3eme ?

En 3e, on calcule souvent le PGCD avec l’algorithme d’Euclide. Je prends les deux nombres, puis j’effectue des divisions euclidiennes successives. À chaque étape, le reste devient le nouveau diviseur. Quand le reste vaut 0, le dernier reste non nul est le PGCD. Cette méthode est simple, rapide et très utilisée au collège.

Comment utiliser l'algorithme d'Euclide ?

Pour utiliser l’algorithme d’Euclide, je divise le plus grand nombre par le plus petit. Je note le reste, puis je recommence en divisant l’ancien diviseur par ce reste. Je poursuis jusqu’à obtenir un reste nul. Le dernier diviseur non nul est alors le PGCD des deux nombres. C’est la méthode de référence pour trouver rapidement un PGCD.

Comment calculer le PGCD avec la division euclidienne ?

Je commence par écrire une division euclidienne : a = b × q + r. Ensuite, je remplace le couple (a, b) par (b, r) et je refais une division. Je continue jusqu’à ce que le reste soit égal à 0. Le PGCD est alors le dernier reste non nul, ou le dernier diviseur utilisé. Cette méthode repose directement sur l’algorithme d’Euclide.

Comment remonter le théorème d'Euclide ?

Remonter le théorème d’Euclide consiste à repartir des divisions successives pour exprimer le PGCD comme combinaison des deux nombres de départ. Je remplace chaque reste par son expression trouvée à l’étape précédente. En remontant ainsi, j’obtiens une écriture du type PGCD = ax + by. Cette technique est utile pour les équations diophantiennes et le théorème de Bézout.

Comment calculer le PGCD à l'aide de l'algorithme d'Euclide ?

Je prends deux entiers positifs, puis j’applique des divisions euclidiennes successives. À chaque fois, le reste obtenu remplace le plus petit des deux nombres. Je répète le procédé jusqu’à ce que le reste soit nul. Le dernier nombre non nul est le PGCD. L’algorithme d’Euclide est très efficace, même avec des nombres assez grands.

Comment calculer le PGCD par l'algorithme ?

Pour calculer le PGCD par l’algorithme, je compare deux nombres et je divise le plus grand par le plus petit. Je récupère le reste, puis je recommence avec le diviseur et le reste. Le processus continue jusqu’à un reste nul. Le dernier diviseur non nul donne le PGCD. C’est une méthode plus rapide que la recherche de tous les diviseurs communs.

Pourquoi l'algorithme d'Euclide s'arrête ?

L’algorithme d’Euclide s’arrête parce que les restes obtenus sont des entiers naturels strictement décroissants et toujours positifs ou nuls. Or, on ne peut pas avoir une suite infinie d’entiers naturels qui diminuent sans fin. On finit donc forcément par atteindre un reste égal à 0. À ce moment-là, le calcul est terminé et le PGCD est trouvé.

Comment trouver le PGCD de 24 et 36 ?

Je prends 36 et 24. Je fais la division euclidienne : 36 = 24 × 1 + 12. Puis 24 = 12 × 2 + 0. Comme le reste est devenu nul, le dernier diviseur non nul est 12. Donc le PGCD de 24 et 36 est 12. Cela montre bien comment fonctionne l’algorithme d’Euclide sur un exemple simple.

Retenez l’idée essentielle : pour appliquer l’algorithme d’Euclide, on enchaîne des divisions euclidiennes jusqu’à obtenir un reste nul. Le dernier reste non nul donne le PGCD. En vous entraînant sur quelques exemples de niveau 3e, la méthode devient vite automatique. Prenez deux nombres, posez les divisions étape par étape et vérifiez toujours vos restes : c’est le meilleur moyen de progresser avec confiance.

Mis à jour le 05 mai 2026