PGCD de deux entiers

Merci !

Fiches
Classe(s) : Tle Générale | Thème(s) : Arithmétique


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.

On fait la division euclidienne de a par b : a=bq1+r1 avec q1 et r1 entiers naturels, 0r1<b. d=PGCDb;r1. Si r1=0, alors b|a et d=b. Sinon…

On fait la division euclidienne de b par r1 : b=r1q2+r2 avec q2 et r2 entiers naturels, 0r2<r1. d=PGCDr1;r2. Si r2=0, alors r1|b et d=r1. Sinon…

On fait la division euclidienne de r1 par r2 : r1=r2q3+r3 avec q3 et r3 entiers naturels, 0r3<r2. d=PGCDr2;r3. Si r3=0, alors r2|r1 et d=r2.

Sinon, on continue les divisions…

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

PGCD12458;3772=PGCD3772;1142=PGCD1142;346=PGCD346;104=PGCD104;34=PGCD34;2=2.

Le PGCD de 12 458 et 3 772 est 2.

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.

Annabac est gratuit en septembre !

Inscris-toi pour en profiter.