Le plus grand commun diviseur de plusieurs entiers est le plus grand entier positif qui les divise tous sans reste. Abrégé PGCD, il sert à réduire des fractions, simplifier des rapports, former des groupes égaux et choisir la plus grande mesure qui s'insère exactement dans plusieurs longueurs.
Les diviseurs communs rendent la définition concrète
Les diviseurs positifs de 18 sont 1, 2, 3, 6, 9 et 18. Ceux de 24 sont 1, 2, 3, 4, 6, 8, 12 et 24. Les communs sont 1, 2, 3 et 6 ; le PGCD vaut donc 6. Lister devient peu pratique avec de grands nombres.
Choisissez deux entiers positifs. Le module affiche chaque division euclidienne et chaque reste au lieu de cacher le raisonnement.
Suivez l'algorithme d'Euclide
Chaque ligne remplace le couple par le diviseur et le reste ; le dernier reste non nul est le PGCD.
La factorisation garde les plus petits exposants
Décomposez chaque nombre en facteurs premiers. Pour chaque nombre premier présent partout, gardez le plus petit exposant et multipliez les puissances retenues. La méthode s'étend à trois entiers ou davantage.
Pour 84 et 126, les facteurs communs sont 2, 3 et 7, une fois chacun. Leur produit est 42. En effet, 84 divisé par 42 vaut 2 et 126 divisé par 42 vaut 3 ; aucune puissance première supplémentaire n'est commune.
L'algorithme d'Euclide traite de grands entiers
Si (a>b>0), divisez (a) par (b), remplacez le couple par (b) et le reste, puis recommencez. Les diviseurs communs sont conservés puisque tout diviseur de (a) et (b) divise aussi (a-qb). Le dernier reste non nul est le PGCD.
Pour 252 et 105, les restes successifs sont 42, 21 puis zéro. Le PGCD est 21, sans factorisation complète. Par convention, (gcd(a,0)=|a|) ; le couple (0,0) est généralement laissé indéfini.
Des identités utiles pour contrôler
L'ordre des entrées ne change pas le PGCD, pris positif. Après division des deux nombres par lui, les quotients sont premiers entre eux. Le produit du PGCD et du PPCM est égal à la valeur absolue du produit des deux entiers.
Un pavage sans découpe
Un sol mesure 252 cm sur 105 cm et doit recevoir les plus grands carreaux carrés sans découpe. Le côté doit diviser les deux dimensions : il mesure 21 cm. On place 12 carreaux par 5, soit 60 au total.
Le PGCD répond à une exigence de divisibilité exacte. Si des chutes, des tolérances ou des mesures arrondies sont admises, un autre critère pratique est nécessaire. Convertissez d'abord toutes les longueurs dans la même unité exacte.
Pour trois entiers, calculez d'abord le PGCD des deux premiers, puis celui du résultat et du troisième. Le PGCD de 48 et 72 vaut 24 ; avec 60, il devient 12. Les signes négatifs ne modifient pas la divisibilité : travaillez sur les valeurs absolues et donnez un résultat positif. La division par le candidat doit produire un entier pour chaque donnée.
