Aller au contenu principal
CalcMax

Calculatrice d’algorithme d’Euclide

Intervalle : 1 – 1 000 000

Intervalle : 1 – 1 000 000

Résultat

21

Plus grand commun diviseur

Étape par étape
1071 = 2 * 462 + 147; 462 = 3 * 147 + 21; 147 = 7 * 21 + 0

L’algorithme d’Euclide donne le plus grand commun diviseur de deux nombres entiers sans jamais factoriser ni l’un ni l’autre. Il repose sur une seule propriété : si a = q * b + r, alors tout ce qui divise à la fois a et b divise aussi r, et tout ce qui divise à la fois b et r divise aussi a — le couple (a, b) et le couple (b, r) ont donc exactement les mêmes diviseurs communs. On remplace le couple par le plus petit et on recommence. À chaque tour les nombres diminuent, et comme ils ne peuvent pas diminuer indéfiniment, l’un des deux finit par valoir zéro ; l’autre est la réponse. Pour 1 071 et 462 les tours sont 1 071 = 2 * 462 + 147, puis 462 = 3 * 147 + 21, puis 147 = 7 * 21 + 0 — le PGCD est donc 21. Trois tours, deux divisions avec reste, et aucune factorisation nulle part. Ce dernier point est la raison pour laquelle cette méthode mérite d’être connue et pas seulement utilisée : pour trouver les facteurs d’un grand nombre il faudrait essayer les diviseurs jusqu’à sa racine carrée, alors que l’algorithme ne divise jamais un nombre que par un nombre qu’il tient déjà, et les valeurs chutent vite. Le couple 610 et 377 — deux nombres de Fibonacci consécutifs — est le pire cas qui existe, et il se termine tout de même en treize tours sur des nombres de trois chiffres. Le nombre de tours n’est pas déterminé par la taille des nombres. 1 000 000 et 999 998 sont bien plus grands que 610 et 377 et se terminent en deux tours, parce que la deuxième étape tombe sur un multiple exact ; à l’inverse 610 et 377 en demandent treize. Le couple qui demande le plus de tours pour sa taille est toujours un couple de nombres de Fibonacci consécutifs : c’est un résultat qui porte un nom, le théorème de Lamé, et c’est la raison pour laquelle la colonne des tours figure à part dans le tableau plus bas. Les deux nombres peuvent être saisis dans n’importe quel ordre. Les ranger par ordre décroissant avant de commencer est un choix de cette page et non une exigence de la méthode, et c’est ce qui fait que 462 et 1 071 affichent exactement les mêmes trois lignes que 1 071 et 462. Les étapes sont écrites sous forme d’équations et non de division posée : chaque tour est a = q * b + r, les points-virgules séparant les tours. Lisez un tour comme une phrase — 1 071 vaut 2 fois 462 plus 147 — et le tour suivant est cette phrase avec les rôles décalés : 462 vaut 3 fois 147 plus 21. Le reste d’un tour devient le diviseur du suivant, et le diviseur devient le dividende.

Trois couples passés par l’algorithme, avec le nombre de tours que chacun demande

Premier nombreDeuxième nombreToursPGCD
1071462321
48180312
3636136

Les deux colonnes de droite sont celles qu’il faut lire ensemble, parce qu’elles ne varient pas ensemble. Les deux premières lignes demandent chacune trois tours, la troisième un seul — mais regardez plutôt la colonne des réponses : 36 et 36 donnent 36 en un tour, tandis que 48 et 180 donnent 12 en trois tours, et 1 071 et 462 donnent 21 en trois tours. La taille ne vous dit rien ni de l’un ni de l’autre. Un couple plus grand n’est pas un calcul plus long, et un calcul plus long ne signifie pas une réponse plus grande. La colonne des tours montre pourquoi : 36 et 36 s’effondrent immédiatement parce que le second nombre divise le premier exactement, donc la boucle s’arrête au premier passage, alors que 48 et 180 descendent par 36 puis par 12 sans qu’aucune de ces étapes soit exacte. Le pire cas en général est un couple de nombres de Fibonacci consécutifs, et c’est pourquoi l’exemple déroulé plus haut utilise 1 071 et 462, le couple avec lequel l’algorithme est habituellement enseigné, plutôt qu’un couple plus grand qui finirait plus vite.

Formule

a = q * b + r, donc pgcd(a, b) = pgcd(b, r) ; on répète jusqu’à r = 0, et b est alors la réponse

a = q * b + r
Un tour de l’algorithme, écrit sous forme d’équation. a est le plus grand des deux nombres à ce tour, b le plus petit, q le nombre de fois entières que b tient dans a, et r ce qui reste. C’est exactement la notation des étapes de la page : 1 071 = 2 * 462 + 147 est un tour
a, b
Les deux nombres comparés. Ils changent d’identité à chaque tour — le b d’un tour devient le a du suivant, et le r devient le nouveau b. Ce remue-ménage explique que les champs de saisie ne s’appellent pas dividende et diviseur : au premier tour 1 071 est le dividende, au deuxième c’est 462, et une étiquette juste pour un tour est fausse pour les autres
q
Le quotient, c’est-à-dire le nombre de fois entières que b tient dans a. Il vaut toujours au moins 1, parce que le couple est rangé par ordre décroissant avant que la boucle ne démarre — c’est aussi pourquoi vous ne verrez jamais q = 0 ici. Le seul tour où q n’a rien de remarquable est le dernier, où le reste est nul et le quotient exact
r
Le reste, toujours plus petit que b et jamais négatif. La règle d’arrêt de l’algorithme est r = 0, affichée comme dernier tour plutôt qu’omise : 147 = 7 * 21 + 0 est la ligne qui dit que la recherche est finie et que 21 est la réponse
pgcd(a, b)
Le plus grand commun diviseur : le plus grand entier qui divise à la fois a et b sans reste. La réponse est le b du dernier tour, prélevé directement dans la boucle plutôt que recalculé. Pour 1 071 et 462 c’est 21, ce qui donne 1 071 = 21 × 51 et 462 = 21 × 22, et aucun entier plus grand ne divise les deux
610 = 1 * 377 + 233
Le tour d’ouverture du pire cas : deux nombres de Fibonacci consécutifs. Tous les quotients y valent 1 et les nombres ne diminuent presque pas, et c’est ce qui fait durer ce couple treize tours. Le théorème de Lamé dit qu’aucun couple de cette taille ne peut en demander davantage

Simplifier une fraction est l’usage de tous les jours. Pour écrire 462/1 071 sous forme irréductible il faut le plus grand commun diviseur des deux, et cette page vous le donne avec sa justification — 21, et les trois tours qui l’ont produit. En divisant le numérateur et le dénominateur par 21 on obtient 22/51, et les étapes affichées permettent de vérifier la simplification au lieu de s’y fier. Le même besoin apparaît chaque fois qu’un rapport doit être réduit : rapports de transmission, formats d’écran, dessins à l’échelle, et deux mesures quelconques que vous voulez exprimer comme une proportion plutôt que comme une paire de nombres. Le deuxième usage est en programmation et en cours, où l’algorithme est enseigné comme le premier vraiment intéressant : il se termine, il est rapide, et il est correct pour une raison qu’on lit dans une seule équation. C’est aussi la façon habituelle de calculer un inverse modulaire — la version étendue promène deux nombres supplémentaires le long des mêmes tours —, étape qui se trouve à l’intérieur de la génération d’une clé RSA. Un troisième usage est la contre-épreuve sur la factorisation. Trouver que 1 071 vaut 3 × 357 et que 462 vaut 2 × 3 × 7 × 11 demande du travail ; trouver que leur plus grand commun diviseur vaut 21 demande trois divisions, donc passer d’abord par cette page vous dit si la simplification sera facile avant que vous ne commenciez. Quand vous ne voulez que la réponse et pas le processus, la calculatrice de PGCD pose la même question sous une forme plus courte et traite plus de deux nombres à la fois ; la calculatrice de PPCM se sert du diviseur pour obtenir le plus petit commun multiple, puisque ppcm = (a / pgcd) * b ; la calculatrice de reste traite ce que signifie un reste isolé quand les nombres peuvent être négatifs, ce que cette page n’a jamais à gérer.

Exemples détaillés

  1. Le couple des manuels : 1 071 et 462

    1. Combien de fois 462 tient-il dans 1 071 ? Deux fois, et 2 × 462 = 924, ce qui laisse 1 071 − 924 = 147
    2. Le couple est maintenant 462 et 147 : 147 tient trois fois dans 462, 3 × 147 = 441, et il reste 21
    3. Le couple est maintenant 147 et 21 : 21 tient exactement sept fois dans 147, et il reste 0
    4. Le reste est nul, donc l’algorithme s’arrête et la réponse est 21

    L’entrée par défaut, et l’exemple avec lequel cet algorithme est habituellement présenté. Deux vérifications valent la peine. Divisez les deux nombres par 21 : vous obtenez 51 et 22, qui n’ont aucun facteur commun, et c’est ce qui fait de 21 le plus grand diviseur commun et pas seulement un diviseur commun. Notez ensuite que rien ici n’a demandé de factoriser : pour trouver les facteurs de 1 071 par divisions successives il faudrait monter jusqu’à 32, alors que l’algorithme n’a jamais divisé un nombre que par un nombre qu’il avait déjà en main. Trois tours, chacun moins coûteux que le précédent.

  2. Un seul tour suffit : 12 et 60

    1. Rangez le couple par ordre décroissant : 60 d’abord, 12 ensuite
    2. 60 = 5 × 12 + 0, donc 12 divise 60 exactement
    3. Le reste est nul tout de suite, donc l’algorithme s’arrête après un seul tour
    4. La réponse est 12 — le plus petit des deux, puisqu’il divise le plus grand

    Le déroulement non trivial le plus court possible, et le cas qui montre pourquoi le dernier tour est affiché au lieu d’être sauté. La ligne 60 = 5 * 12 + 0 contient toute la réponse : elle dit que le reste a atteint zéro, ce qui est la seule façon dont cet algorithme s’arrête. Supprimez cette ligne et les étapes seraient vides, sans que le lecteur puisse distinguer une réponse en un tour d’une page qui n’aurait pas tourné. Chaque fois qu’un nombre divise l’autre exactement, le plus grand commun diviseur est simplement le plus petit des deux.

  3. Nombres premiers entre eux : 9 et 20

    1. 20 = 2 × 9 + 2, donc le couple devient 9 et 2
    2. 9 = 4 × 2 + 1, donc le couple devient 2 et 1
    3. 2 = 2 × 1 + 0, donc l’algorithme s’arrête
    4. La réponse est 1, ce qui signifie que 9 et 20 n’ont aucun diviseur commun au-dessus de 1

    Un plus grand commun diviseur de 1 est une vraie réponse, pas un échec, et elle porte un nom : les nombres sont premiers entre eux. C’est aussi le signe que la fraction 9/20 est déjà irréductible, donc qu’aucune simplification n’est disponible. Remarquez que les tours ne se sont pas effondrés — l’algorithme est descendu jusqu’à 1 en trois étapes, parce qu’aucun des deux nombres n’a jamais divisé l’autre exactement. Les couples premiers entre eux sont le cas courant quand les nombres grandissent : la probabilité que deux nombres tirés au hasard partagent un diviseur décroît vite, et c’est précisément ce qui rend la méthode utile pour construire un inverse modulaire en cryptographie.

Limites

Les deux nombres doivent être entiers, et tous deux compris entre 1 et 1 000 000. Zéro est refusé plutôt que traité comme un cas particulier. Le plus grand commun diviseur de a et de 0 vaut a, ce qui est une réponse parfaitement valable, mais cette page ne peut pas la montrer : le premier tour s’écrirait a = q * 0 + r, et ce q n’existe pas. Plutôt que d’afficher un processus troué, la page décline l’entrée. Les nombres négatifs sont refusés pour la même raison — les étapes telles qu’elles sont écrites supposent que les deux nombres valent au moins 1, et un opérande négatif exigerait une règle sur ce que signifient le quotient et le reste, règle que cette page n’énonce nulle part. Le plafond de 1 000 000 ne concerne pas l’algorithme, qui tournerait volontiers sur des nombres bien plus grands ; il est là pour que chaque soustraction, multiplication et reste en chemin soit exact en arithmétique double ordinaire, et pour que les étapes affichées ne puissent pas atteindre une longueur qui cesse d’être lisible. Deux nombres assez petits peuvent tout de même produire beaucoup de tours — 610 et 377 en demandent treize — mais le compte reste borné en pratique par ce plafond, et le tableau de référence comporte une colonne de tours pour que vous la voyiez varier. Les étapes sont affichées sous forme d’équations — a = q * b + r, séparées par des points-virgules — et non de division posée : si vous cherchez le crochet de division habituel, cette page ne vous le donnera pas. Les entrées sont interchangeables : la page les range par ordre décroissant avant de commencer, donc vous ne pouvez pas vous en servir pour voir à quoi ressemblerait 3 = 0 * 5 + 3, puisque ce tour n’est jamais produit. Si vos nombres peuvent être négatifs, ou si vous voulez que la convention de reste soit explicitée, la calculatrice de reste est la page faite pour cette question.

Questions fréquentes

Qu’est-ce que le plus grand commun diviseur, en une phrase ?
Le plus grand entier qui divise les deux nombres exactement, sans laisser de reste. Pour 1 071 et 462 c’est 21 : 1 071 = 21 × 51 et 462 = 21 × 22, et 51 et 22 n’ont aucun facteur commun, ce qui fait de 21 le plus grand. Notez que 3 et 7 divisent aussi les deux nombres — ce sont des diviseurs communs, simplement pas le plus grand. Le résultat principal de la page est toujours ce nombre, et les étapes affichées en dessous en sont la preuve.
Pourquoi la dernière étape se termine-t-elle toujours par + 0 ?
Parce qu’un reste nul est la seule chose qui arrête l’algorithme. La boucle remplace le couple par un couple plus petit — le second nombre et le reste — et les nombres diminuent à chaque tour, donc ils doivent finir par atteindre zéro. 147 = 7 * 21 + 0 est le tour où cela se produit, et le plus grand commun diviseur est le diviseur de ce tour, 21. La page l’affiche plutôt que de le cacher, parce qu’une liste d’étapes qui s’arrêterait au dernier reste non nul laisserait le lecteur conclure tout seul que la recherche était finie.
L’ordre dans lequel je saisis les deux nombres a-t-il une importance ?
Non. La page les range par ordre décroissant avant le premier tour, donc 462 et 1 071 produisent exactement les trois mêmes lignes que 1 071 et 462. C’est un choix et non une propriété de l’algorithme — la règle pgcd(a, b) = pgcd(b, a) fait que les deux ordres donnent la bonne réponse — mais sans ce tri la première ligne s’écrirait 3 = 0 * 5 + 3 pour le couple 3 et 5, ce qui est une division licite mais donne l’impression que diviser un petit nombre par un plus grand fait partie de la méthode. C’est aussi la raison pour laquelle les champs s’appellent premier nombre et deuxième nombre plutôt que dividende et diviseur : ces deux rôles s’échangent à chaque tour.
Que signifie une réponse égale à 1 ?
Que les deux nombres n’ont aucun diviseur commun au-dessus de 1, ce qui est une réponse complète et non un échec. Ces nombres sont dits premiers entre eux, et le couple 9 et 20 de cette page en est un exemple. Cela vous apprend aussi quelque chose de pratique : la fraction 9/20 est déjà irréductible, donc aucune simplification n’est possible. Quand les nombres grandissent, les couples premiers entre eux deviennent le cas courant, et c’est pourquoi la méthode compte en cryptographie — construire une clé RSA revient à trouver des nombres qui ne partagent aucun facteur avec un nombre donné.
Est-ce que des nombres plus grands demandent toujours plus de tours ?
Non, et le tableau de référence est là pour le rendre concret. 1 000 000 et 999 998 se terminent en deux tours, tandis que 610 et 377 — trois chiffres chacun — en demandent treize. Ce qui impose beaucoup de tours n’est pas la taille mais la lenteur avec laquelle les nombres diminuent, et les couples qui diminuent le plus lentement sont les nombres de Fibonacci consécutifs, où chaque reste est proche du diviseur. Ce résultat est le théorème de Lamé, et il plafonne le nombre de tours à une valeur qui ne croît qu’avec le nombre de chiffres : c’est pourquoi l’algorithme est considéré comme rapide.
En quoi est-ce différent de simplement factoriser les deux nombres ?
La factorisation demande beaucoup plus de travail, et c’est un travail que cette page ne fait jamais. Pour factoriser 1 071 par divisions successives il faudrait essayer les diviseurs jusqu’à sa racine carrée, soit environ 32 ; l’algorithme, lui, divise un nombre par un nombre qu’il tient déjà et se termine en trois tours. Sur des nombres aussi petits l’écart est invisible, mais la factorisation devient spectaculairement plus difficile à mesure que les nombres grandissent, alors que la division euclidienne ne s’en aperçoit presque pas. Cet écart est toute la raison pour laquelle l’algorithme est encore enseigné, et c’est aussi pourquoi la réponse sort de la boucle au lieu de venir d’un second calcul : faire les deux risquerait de faire diverger les étapes affichées d’avec le nombre imprimé juste au-dessus.

Références

Calculatrices liées

Calculatrice de PGCDTous les diviseurs communs de deux à dix nombres.Calculatrice de PPCMLes quatre premiers multiples communs de deux à dix nombres.Calculatrice de resteQuotient et reste, selon la convention de signe choisie.Calculatrice de tri croissantTrie une liste de nombres du plus petit au plus grand.Calculatrice de moduloUn reste toujours positif, quels que soient les signes.