Mathématiques 45: Arithmétique
Le Plus Grand Commun Divisuer (PGCD)
1. Définition du PGCD de deux nombres
Le plus grand diviseur d'un nombre, c'est lui même.
Le plus grand commun diviseur (PGCD) de deux nombres
est le diviseur commun à ces deux nombres, mais le
plus grand.
Pour trouver le PGCD de deux nombres entiers, on dispose
de trois façons.
2. PGCD de deux nombres méthode de listes de diviseurs
2.1. La méthode
On dresse la liste des diviseurs des deux
nombres selon les étapes suivantes:
• On développe les deux nombres en produit de
facteurs premiers,
•On note tous les facteurs communs aux deux nombres ,
•On fait le produit de ses facteurs communs,
•Ce produit est le PGCD de ses nombes.
2.2. Exemple
On cherche le pgcd de 420 et 45.
• Liste des diviseurs de 420:
420 = 2 x 2 x 3 x 5 x 7 = 22 x 3 x 5 x 7
• Liste des diviseurs de: 45
45 = 3 x 3 x 5 = 32 x 5
15 est le plus grand commun diviseur, donc
pgcd(450,45)= 15
3. PGCD de deux nombres
méthode de soustractions successives
3.1. La méthode
On procède selon les étapes suivantes:
• On soustrait le plus petit des deux nombres du plus grand,
• On note les deux plus petits nombres parmi les trois,
• On soustrait le plus petit des deux nombres du plus grand,
• On note les deux plus petits nombres parmi les trois,
• On soustrait le plus petit des deux nombres du plus grand,
• ...
• On continue jusqu'à ce qu'on trouve zéro.
Le pgcd est le dernier résultat non nul.
3.2. Exemple
On cherche le pgcd de 420 et 45.
• On soustrait le plus petit des deux nombres du plus grand:
420 - 45 = 375
• On note les deux plus petits nombres parmi les trois:
375 et 45 et on recommence:
• 375 - 45 = 330
• 330 - 45 = 285
• 285 - 45 = 240
• 240 - 45 = 195
• 195 - 45 = 150
• 150 - 45 = 105
• 105 - 45 = 60
• 60 - 45 = 15
• 45 - 15 = 30
• 30 - 15 = 15 : dernir résultat non nul.
• 15 - 15 = 0 on trouve zéro.
Le pgcd est le dernier résultat non nul = 15 .
4. PGCD de deux nombres:
Algorithme d'Euclide
4.1. La méthode
On considère deux nombres a et b, a le plus grand.
On procède selon les étapes suivantes:
• On fait la division euclidienne du plus grand nombre (a) par le plus petit (b):
a = b x q + r,
• On recommence la division avec le diviseur (b) et le reste (r) de la division précédente:
b = r x q' + r'
• On répète les deux étapes,
• On s'arrête lorsque le reste est nul.
Le Pgcd est le dernier reste non nul.
4.2. Exemple
On cherche le pgcd de 420 et 45.
420 = 45 x 9 + 15
45 = 15 x 3 + 0
Le Pgcd est le dernier reste non nul = 15 .
Vérifier vos résulats par ce logiciel
|