ArithmétiqueMéthode · Glossaire
algorithme des différences
Algorithme de calcul du plus grand commun diviseur (PGCD) de deux entiers, fondé sur la propriété : PGCD(a, b) = PGCD(b, a − b) lorsque a > b. Le procédé consiste à remplacer à chaque étape le plus grand des deux nombres par leur différence, jusqu'à l'égalité des deux termes, qui donne le PGCD. Bien que reposant sur le même principe que l'algorithme d'Euclide, cette méthode par différences est moins efficace : elle nécessite en général un plus grand nombre d'itérations, notamment lorsque les deux entiers sont très proches.
Sommaire
Ce que vous allez apprendre
- Appliquer la règle de soustraction jusqu'à l'égalité des deux valeurs.
- Recalculer le PGCD de 1 071 et 462 en onze soustractions.
- Justifier la conservation du PGCD à chaque étape.
- Reconnaître les cas du zéro, des entiers négatifs et de la convergence lente.
- Comparer la méthode soustractive à l'algorithme d'Euclide par divisions.
En clair
Prenons 1 071 jetons rouges et 462 jetons noirs. Retirer 462 jetons de chaque côté ne change pas la taille des groupes égaux qui peuvent partager les deux quantités. Il reste donc à comparer 609 et 462, puis à recommencer avec la plus grande quantité.
Les nombres diminuent sans perdre leurs diviseurs communs. Quand ils deviennent égaux, ici à 21, cette valeur est le plus grand nombre qui divise les deux quantités de départ : leur PGCD.
Définition
L'algorithme des différences calcule le plus grand commun diviseur de deux entiers strictement positifs par soustractions successives. Les deux valeurs courantes sont notées a et b. Si a est supérieur à b, on remplace a par a − b ; si b est supérieur à a, on remplace b par b − a. L'autre valeur reste inchangée.
La méthode repose sur l'invariance lorsque a > b. En effet, un entier divise à la fois a et b si et seulement s'il divise b et la différence a − b. Chaque soustraction conserve donc exactement les diviseurs communs, tandis que la somme a + b diminue. Pour des entiers positifs, le procédé atteint nécessairement une paire égale. La valeur commune est alors le PGCD des nombres initiaux.
Cette procédure est une forme soustractive de l'algorithme d'Euclide. La version usuelle remplace plusieurs soustractions identiques par une division euclidienne et son reste. Elle aboutit au même PGCD, généralement en moins d'étapes.
Le principe
On part de deux entiers strictement positifs a et b. Tant qu'ils sont différents, on soustrait le plus petit du plus grand et l'on conserve le plus petit. Autrement dit, si a > b, la paire (a, b) devient (a − b, b) ; si b > a, elle devient (a, b − a). Dès que les deux valeurs sont égales, leur valeur commune est le PGCD recherché.
Quand l'utiliser
La procédure directe demande deux entiers strictement positifs. À chaque étape, il faut comparer les deux valeurs, soustraire la plus petite de la plus grande et conserver l'autre. Le résultat obtenu est leur PGCD positif. Si les nombres sont déjà égaux, aucune soustraction n'est nécessaire.
Avec une valeur nulle, par exemple (35, 0), soustraire 0 ne fait pas avancer le calcul. On applique alors directement la convention PGCD(35, 0) = 35. Avec des entiers négatifs, on commence par prendre leurs valeurs absolues. Pour de grands nombres ou des valeurs très proches, l'algorithme d'Euclide par divisions est préférable.
Un exemple, pas à pas
Calculons le PGCD de 1 071 et 462. Les données sont les deux entiers strictement positifs 1 071 et 462 ; à chaque étape, la plus grande valeur est remplacée par leur différence.
1. Comme 1 071 > 462, on obtient (609, 462), puis (147, 462).
2. La seconde valeur est maintenant la plus grande : (147, 462) devient (147, 315), puis (147, 168), puis (147, 21).
3. On retranche ensuite 21 à la première valeur : (126, 21), (105, 21), (84, 21), (63, 21), (42, 21), puis (21, 21).
Les deux termes sont égaux après onze soustractions. Le résultat est donc PGCD(1 071, 462) = 21. La chaîne complète permet de suivre les valeurs sans perdre l'invariant.
Le contrôle par divisions donne 1 071 = 2 × 462 + 147, puis 462 = 3 × 147 + 21 et 147 = 7 × 21. Comme 21 divise aussi exactement 1 071 et 462, le résultat est vérifié.
En pratique
À la main, l'algorithme des différences convient à de petits entiers : il ne demande que de comparer et de soustraire. Dès que la même soustraction se répète, une division euclidienne regroupe ces étapes et raccourcit le calcul.
Pour expliquer pourquoi le calcul du PGCD fonctionne, chaque paire rend visible la conservation des diviseurs communs. Pour calculer vite, on préfère la version d'Euclide par restes, qui conserve le même principe sans écrire toutes les soustractions.
Dans un programme, une boucle de soustractions constitue un exercice simple sur les conditions et l'arrêt. Pour des entrées importantes, l'opération modulo remplace avantageusement les longues séries de soustractions.
À ne pas confondre
L'algorithme d'Euclide par divisions. Il remplace le plus grand nombre par le reste de sa division par le plus petit. Pour 1 071 et 462, il produit directement le reste 147, là où la méthode des différences effectue deux soustractions. Les deux procédures calculent le même PGCD, mais leurs étapes diffèrent.
L'algorithme d'Euclide étendu. Il calcule en plus des coefficients de Bézout. L'algorithme des différences décrit ici s'arrête au PGCD : obtenir des entiers u et v tels que 1 071u + 462v = 21 demande de mémoriser et de recombiner les opérations.
Limites et pièges
Valeurs très proches. Avec 100 et 99, une première soustraction donne (1, 99), puis il faut retrancher 1 encore 98 fois pour atteindre (1, 1). Le symptôme est une longue répétition du même geste. Une division euclidienne évite cette convergence lente.
Zéro. Avec (35, 0), remplacer 35 par 35 − 0 reproduit la même paire : la boucle ne s'arrête pas. Il faut traiter ce cas séparément avec PGCD(35, 0) = 35. Pour (0, 0), la boucle ne fournit aucun résultat ; de nombreux cadres adoptent séparément la convention PGCD(0, 0) = 0.
Entiers négatifs. La règle « soustraire le plus petit du plus grand » n'assure plus une diminution vers l'égalité si les signes sont conservés. Il faut d'abord remplacer chaque entrée par sa valeur absolue, puis exécuter l'algorithme sur des entiers positifs.
Coût du calcul. Le nombre de soustractions dépend de la taille et du rapport des entrées. Une suite très longue ne signale pas une erreur mathématique, mais une méthode peu efficace ; l'opération modulo est alors le bon remplacement.
Pour aller plus loin
L'entrée PGCD précise ce que mesure ce diviseur commun maximal et rappelle ses propriétés arithmétiques.
La fiche algorithme d'Euclide présente la version par divisions, qui regroupe plusieurs soustractions en une seule étape de reste.
L'article Algorithme d'Euclide et cætera ouvre sur d'autres prolongements de cette idée fondamentale en arithmétique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres