PGCD de deux entiers naturels
Définition
Soient a et b deux entiers naturels non tous les deux nuls.
On note D(a;b) l’ensemble des diviseurs communs de a et b.
L’ensemble D(a;b) contient un plus grand élément, noté PGCD(a;b). C’est le plus grand diviseur commun de de a et b.
Exemples
D(12;20)=\{-4;-2;-1;1;2;4\} donc PGCD(12;20)=4.
D(6;15)=\{-3;-1;1;3\} donc PGCD(6;15)=3.
Déterminer le PGCD avec la TI 83 Premium CE Python
Au clavier
A l’écran
Appuyer sur la touche math, sélectionner la colonne NBRE et sélectionner 9: pgcd( dans le menu déroulant.
Saisir les deux nombres, par exemple 12 et 20 puis valider par entrer.
Exercice n°1
1. Déterminer les diviseurs de 92 et de 64 dans \mathbf{Z}.
2. En déduire le PGCD de 92 et de 64.
Exercice n°2
1. Déterminer les diviseurs de 286 dans \mathbf{Z}.
2. En déduire le PGCD de 286 et de 1034.
Algorithme d’Euclide
Soient a et b deux entiers naturels non nuls.
L’algorithme d’Euclide consiste à effectuer la division de a par b puis successivement les divisions du diviseur par le reste de la ligne précédente. A un moment le reste est nul et le PGCD sera le dernier reste non nul.
Voici un exemple où on cherche le PGCD(12;20). Le dernier reste non nul est 4 donc PGCD(20;12)=4
Voici un autre exemple où on cherche le PGCD(42;36). Le dernier reste non nul est 6 donc PGCD(42;36)=6
Exercice n°3
A l’aide de l’algorithme d’Euclide, déterminer le PGCD de 1440 et 162.
Exercice n°4
A l’aide de l’algorithme d’Euclide, déterminer le PGCD de 4539 et 1958.
Exercice n°5
A l’aide de l’algorithme d’Euclide, déterminer le PGCD de 9185 et 2004.
On veut déterminer les diviseurs de 92 et de 64 dans \mathbf{Z}.
- On peut décomposer 92 en produit de facteurs premiers.
92
46
23
1
2
2
23
92=2^2\times 23
Les diviseurs sont -92;-46;-23;-4;-2;-1;1;2;4;23;46;92
- On peut décomposer 64 en produit de facteurs premiers.
64
32
16
8
4
2
1
2
2
2
2
2
2
64=2^6
Les diviseurs sont -64;-32;-16;-8;-4;-2;-1;1;2;4;8;16;32;64
Les diviseurs de 92 sont -92;-46;-23;-4;-2;-1;1;2;4;23;46;92.
Les diviseurs de 64 sont -64;-32;-16;-8;-4;-2;-1;1;2;4;8;16;32;64.
Les diviseurs communs sont -4;-2;-1;1;2;4.
Donc PGCD(92;64)=4.
On veut déterminer les diviseurs de 286 dans \mathbf{Z}.
On peut décomposer 286 en produit de facteurs premiers.
286
143
13
1
2
11
13
286=2\times 11\times 13
Les diviseurs sont -286;-143;-26;-22;-13;-11;-2;-1;1;2;11;13;22;26;143;286.
On veut en déduire le PGCD(286;1034).
Les diviseurs de 286 sont -286;-143;-26;-22;-13;-11;-2;-1;1;2;11;13;22;26;143;286.
On divise 1084 par ces diviseurs en commençant par le plus grand, quand le résultat est un nombre entier on s’arrête.
Donc PGCD(286;1034)=22
Après avoir utilisé l’Algorithme d’Euclide, le dernier reste non nul trouvé est 18 donc PGCD(1440;162)=18
Après avoir utilisé l’Algorithme d’Euclide, le dernier reste non nul trouvé est 89 donc PGCD(4539;1958)=89
Après avoir utilisé l’Algorithme d’Euclide, le dernier reste non nul trouvé est 167 donc PGCD(9185;2004)=167
