La détermination du PGCD de deux entiers permet, entre autres, en mathématiques de simplifier des écritures fractionnaires, et dans la vie courante d’optimiser des pavages ou des répartitions.
I. Détermination du PGCD de deux entiers
1) Définition
Le PGCD – ou plus grand commun diviseur – de deux entiers relatifs a et b non tous les deux nuls est le plus grand des diviseurs positifs communs à a et à b. On le note PGCDa ; b ou bien a∧b.
Remarque : PGCDa ; b=PGCDa ; b . Dans la suite, on pourra ne considérer que des entiers naturels.
À noter
Les calculatrices disposent d’une fonction, parfois notée GCD, permettant d’obtenir le PGCD de deux entiers donnés.
2) L’algorithme d’Euclide
Cette méthode est basée sur la « propriété fondamentale » suivante :
Soit a et b deux entiers naturels tels que 0<b<a. Si a=bq+r avec b et r entiers naturels, alors PGCDa ; b=PGCDb ; r.
Principe de l’algorithme d’Euclide
a et b entiers naturels tels que 0<b<a ; d=PGCDa ; b.
Au bout d’un nombre fini d’étapes (nombre variable suivant les nombres a et b), on obtient un reste nul, l’algorithme s’arrête. d est le dernier reste non nul.
II. Propriétés
Les diviseurs communs à deux entiers relatifs non nuls sont les diviseurs de leur PGCD.
Si a et b sont deux entiers relatifs non tous les deux nuls et k∈ ℕ∗ :
PGCDka ; kb=k×PGCDa ; b.
Méthodes
1) Déterminer un PGCD à l’aide de l’algorithme d’Euclide
Déterminer à l’aide de l’algorithme d’Euclide le PGCD d de a=12 458 et b=3 772.
Conseils
Effectuez des divisions successives, en commençant par la division euclidienne de a par b.
Solution
12 458=3 772×3+1 1423 772=1 142×3+3461 142=346×3+104346=104×3+34104=34 × 3+234=2×17+0
2 Déterminer un rangement optimal
On dispose d’une caisse ayant la forme d’un parallélépipède rectangle de base carrée de côté 882 cm, de hauteur 945 cm, que l’on souhaite remplir, sans laisser d’espace, avec des cubes tous identiques d’arête d (en cm), avec d entier naturel.
a. Déterminer la plus grande valeur (entière) possible de d.
b. Déterminer toutes les valeurs entières possibles de d.
Conseils
Déterminez le PGCD de 945 et 882.
Solution
Toute valeur de d qui convient est un diviseur commun à 945 et 882.
a. Le PGCD de 945 et 882 est 63 (calculatrice ou algorithme d’Euclide), donc la plus grande valeur possible de d est 63.
b. Les valeurs entières possibles de d sont les diviseurs de 63, c’est-à-dire : 1, 3, 7, 9, 21 et 63.