L’algorithme d’Euclide trouve le plus grand commun diviseur (PGCD) de deux nombres par divisions successives, sans factoriser. Pour 462/1071, trois divisions suffisent : le PGCD vaut 21 et la fraction devient 22/51. Si vous ne voulez que le résultat, la calculatrice de PGCD le donne tout de suite ; ce guide explique la méthode à la main et pourquoi elle aboutit toujours au PGCD.
L’idée tient en une phrase : le PGCD de deux nombres ne change pas si vous remplacez le plus grand par le reste de sa division par le plus petit. Vous répétez jusqu’à obtenir un reste de 0, et le dernier diviseur utilisé est le PGCD.
Chaque ligne vérifie dividende = quotient × diviseur + reste, avec un reste inférieur au diviseur. Seuls le diviseur et le reste passent à la ligne suivante, pas le quotient. Le produit en croix de la vérification est le même que celui qui sert à comparer des fractions, et diviser les deux termes par le même nombre est ce qui distingue simplifier de multiplier les deux termes par un même nombre, comme l’explique la page sur les fractions égales.
Pourquoi le reste suffit
Si a = q × b + r, tout nombre qui divise a et b divise aussi r, puisque r = a − q × b. Et inversement : ce qui divise b et r divise a. Les couples (a, b) et (b, r) ont donc les mêmes diviseurs communs, et le plus grand d’entre eux est le même. Ainsi PGCD(a, b) = PGCD(b, r). Comme chaque reste est plus petit que le précédent, la chaîne descend jusqu’à 0.
La même idée se voit avec des carrés. Le rectangle de 1071 par 462 se recouvre avec deux carrés de côté 462 ; dans la bande restante, il en tient trois de côté 147, et dans la dernière bande, sept de côté 21. Le plus petit carré qui remplit tout sans trou mesure 21 : c’est le PGCD.
Exemple résolu : simplifier 462/1071
Vous voulez réduire 462/1071 à sa fraction irréductible et vous ne voyez aucun diviseur commun à première vue.
- Divisez le plus grand par le plus petit. 1071 = 2 × 462 + 147.
- Passez au couple diviseur et reste. Ce sont maintenant 462 et 147 : 462 = 3 × 147 + 21.
- Recommencez avec le nouveau couple. Ce sont 147 et 21 : 147 = 7 × 21 + 0. Le reste est 0, la chaîne s’arrête.
- Prenez le dernier diviseur. Le PGCD est 21.
- Divisez le numérateur et le dénominateur par 21. 462 ÷ 21 = 22 et 1071 ÷ 21 = 51.
Résultat : 462/1071 = 22/51.
Vérification : en croix, 462 × 51 = 23 562 et 1071 × 22 = 23 562, donc les deux fractions sont égales. De plus, 22 = 2 × 11 et 51 = 3 × 17 n'ont aucun facteur commun.
Deuxième exemple, avec cinq divisions
Pour 3600/4284, commencez par le plus grand nombre, 4284. La chaîne est :
- 4284 = 1 × 3600 + 684
- 3600 = 5 × 684 + 180
- 684 = 3 × 180 + 144
- 180 = 1 × 144 + 36
- 144 = 4 × 36 + 0
Le PGCD est 36, et 3600 ÷ 36 = 100 avec 4284 ÷ 36 = 119 : la fraction devient 100/119. Si vous commencez par le plus petit, la première division a un quotient de 0 et ne fait qu’échanger le couple ; le résultat est le même, avec une étape de plus.
Euclide ou facteurs premiers
Pour un PGCD, il y a deux chemins, et chacun gagne sur un terrain différent.
| Méthode | Ce que vous faites | Résultat | Quand la choisir |
|---|---|---|---|
| Euclide | Vous divisez avec reste jusqu'à obtenir 0 | 5 divisions, PGCD 36 | Grands nombres, ou quand vous n'avez besoin que du PGCD |
| Facteurs premiers | Vous factorisez et prenez les facteurs communs avec le plus petit exposant | 2² × 3² = 36 | Petits nombres, ou quand vous voulez aussi le PPCM |
Avec 4284 = 2² × 3² × 7 × 17 et 3600 = 2⁴ × 3² × 5², la factorisation oblige à trouver tous les nombres premiers, et un grand facteur allonge la recherche. Euclide ne les cherche jamais. Si vous avez besoin du PPCM en plus du PGCD, la décomposition en facteurs premiers le donne directement, et le guide sur la différence entre PGCD et PPCM explique quand utiliser chacun. Les critères de divisibilité font gagner des étapes quand le diviseur commun saute aux yeux.
Une erreur qui ressemble à un résultat
L’erreur la plus courante consiste à reporter le quotient au lieu du reste, et elle produit un PGCD qui paraît plausible.
Une autre erreur voisine est de s’arrêter sur un petit reste sans attendre le 0 : le PGCD est le dernier diviseur, pas le premier reste qui vous semble commode. Et pour simplifier, il faut diviser les deux termes par le PGCD, pas un seul, sinon la valeur change.
Quand l’utiliser et où aller ensuite
Euclide travaille sur deux entiers à la fois et ne renvoie que le PGCD. Pour de petites fractions comme 6/8, repérer le 2 à l’œil est plus rapide. Pour vous entraîner avec n’importe quelle fraction, l’outil pour simplifier des fractions applique le PGCD et donne la forme irréductible. Si d’autres écritures d’une fraction vous intéressent, le guide sur les fractions continues et égyptiennes reprend ces mêmes divisions : les quotients de la chaîne sont les termes de la fraction continue.