PGCD de deux entiers

icône de pdf
Signaler

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 ab.

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=12458 et b=3772.

Conseils

Effectuez des divisions successives, en commençant par la division euclidienne de a par b.

Solution

12458=3772×3+11423772=1142×3+3461142=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.