Comment calculer le PGCD avec l'algorithme d'Euclide ?
Tapez vos nombres : le PGCD, le PPCM et toutes les divisions s'affichent aussitôt. Le bouton « Ajouter un nombre » va jusqu'à dix entiers, et la case à cocher ajoute la méthode des facteurs premiers.
Le PGCD (plus grand commun diviseur) est le plus grand entier qui divise tous les nombres sans reste. L'algorithme d'Euclide le trouve sans chercher la liste des diviseurs : on divise le plus grand nombre par le plus petit, puis on recommence en divisant l'ancien diviseur par le reste obtenu, jusqu'à tomber sur un reste nul. Le dernier reste non nul est le PGCD.
Pourquoi cela marche-t-il ? Dans la division a = b × q + r, tout nombre qui divise a et b divise aussi r = a - b × q, et tout nombre qui divise b et r divise a. Les deux couples ont donc exactement les mêmes diviseurs communs : PGCD(a ; b) = PGCD(b ; r). Les restes diminuent à chaque tour, donc l'algorithme s'arrête toujours.
Exemple avec 252 et 198, les nombres chargés dans l'outil : quatre divisions suffisent, et le dernier reste non nul vaut 18. Donc PGCD(252 ; 198) = 18.
| Division | Dividende | Diviseur | Quotient | Reste |
|---|---|---|---|---|
| 252 = 198 × 1 + 54 | 252 | 198 | 1 | 54 |
| 198 = 54 × 3 + 36 | 198 | 54 | 3 | 36 |
| 54 = 36 × 1 + 18 | 54 | 36 | 1 | 18 |
| 36 = 18 × 2 + 0 | 36 | 18 | 2 | 0 |
Comment calculer le PPCM de deux nombres ?
Le PPCM (plus petit commun multiple) est le plus petit entier strictement positif qui est à la fois multiple de tous les nombres. Pour deux nombres, une relation le donne directement à partir du PGCD : PGCD(a ; b) × PPCM(a ; b) = a × b. On en tire PPCM(a ; b) = a × b ÷ PGCD(a ; b).
Avec 252 et 198 : 252 × 198 = 49 896, et 49 896 ÷ 18 = 2 772. On vérifie que 2 772 = 252 × 11 = 198 × 14. Autre exemple, 48 et 180 : 180 = 48 × 3 + 36, puis 48 = 36 × 1 + 12, puis 36 = 12 × 3 + 0, donc le PGCD vaut 12 et le PPCM vaut 48 × 180 ÷ 12 = 8 640 ÷ 12 = 720.
Le PPCM sert à trouver le plus petit dénominateur commun de deux fractions (1/48 + 1/180 se calcule sur 720) ou à savoir quand deux cycles se recalent : deux bus qui partent ensemble, l'un toutes les 12 minutes et l'autre toutes les 18 minutes, repartent ensemble toutes les 36 minutes, car PPCM(12 ; 18) = 36.
Comment trouver le PGCD et le PPCM de trois nombres ou plus ?
On avance de proche en proche, deux nombres à la fois : PGCD(a ; b ; c) = PGCD(PGCD(a ; b) ; c), et de même pour le PPCM. Pour 12, 18 et 30 : PGCD(12 ; 18) = 6, puis PGCD(6 ; 30) = 6. Côté PPCM : PPCM(12 ; 18) = 36, puis PPCM(36 ; 30) = 36 × 30 ÷ 6 = 180.
Attention, la relation PGCD × PPCM = produit ne vaut que pour deux nombres. Ici, 6 × 180 = 1 080 alors que 12 × 18 × 30 = 6 480. L'outil l'applique donc paire par paire, jamais aux trois nombres d'un coup.
Avec plusieurs nombres, il faut aussi distinguer deux notions. 6, 10 et 15 sont premiers entre eux dans leur ensemble (aucun diviseur commun aux trois, sauf 1), mais pas deux à deux : 6 et 10 partagent 2, 6 et 15 partagent 3, 10 et 15 partagent 5. Leur PPCM vaut 30. L'outil affiche les deux informations.
Quelle est la méthode par décomposition en facteurs premiers ?
On écrit chaque nombre comme un produit de nombres premiers : 252 = 2² × 3² × 7 et 198 = 2 × 3² × 11. Le PGCD garde les facteurs communs à tous les nombres, chacun avec son plus petit exposant : 2 × 3² = 18. Le PPCM garde tous les facteurs rencontrés, chacun avec son plus grand exposant : 2² × 3² × 7 × 11 = 2 772. On retrouve les résultats d'Euclide.
Cette méthode est pratique avec de petits nombres et montre bien la structure des diviseurs. Pour de grands nombres, l'algorithme d'Euclide est bien plus rapide, car décomposer un grand nombre en facteurs premiers demande beaucoup d'essais.
| Nombres | PGCD | PPCM | Remarque |
|---|---|---|---|
| 252 et 198 | 18 | 2 772 | 18 × 2 772 = 252 × 198 |
| 48 et 180 | 12 | 720 | 720 = 48 × 15 = 180 × 4 |
| 36 et 12 | 12 | 36 | 12 divise 36 |
| 17 et 5 | 1 | 85 | premiers entre eux |
| 12, 18 et 30 | 6 | 180 | calcul de proche en proche |
| 6, 10 et 15 | 1 | 30 | pas premiers entre eux deux à deux |
Quelles erreurs éviter avec le PGCD et le PPCM ?
- Confondre les deux : le PGCD est toujours inférieur ou égal au plus petit des nombres, le PPCM toujours supérieur ou égal au plus grand. Un PGCD plus grand que l'un des nombres signale une erreur.
- Prendre le dernier reste au lieu du dernier reste non nul : le reste final vaut toujours 0, c'est le reste juste avant qui donne le PGCD.
- Appliquer PGCD × PPCM = a × b à trois nombres ou plus : la relation est fausse dans ce cas.
- Oublier le cas où un nombre divise l'autre : pour 36 et 12, le PGCD est 12 et le PPCM 36, sans calcul.
- Confondre « premiers entre eux » et « nombres premiers » : 8 et 15 sont premiers entre eux (PGCD égal à 1) alors qu'aucun des deux n'est premier.
- Mettre un zéro : par convention PGCD(a ; 0) = a, mais le PPCM avec 0 n'a pas d'intérêt pratique. L'outil demande des entiers strictement positifs.