Sommaire
Méthode 1Par la méthode de l'algorithme d'Euclide 1Poser la division euclidienne du plus grand des deux entiers par le plus petit 2Poser les divisions successives des diviseurs par les restes 3Identifier le dernier reste non nulMéthode 2Par la méthode des soustractions successives 1Poser la différence du plus grand nombre par le plus petit 2Poser les soustractions successives 3Identifier le dernier résultat non nulMéthode 3A l'aide de PGCD \left(k\times a ; k \times b\right) = k \times PGCD \left(a;b\right) 1Déterminer le diviseur commun 2Réciter le cours 3ConclureMéthode 4Par la décomposition en facteurs premiers 1Décomposer les deux nombres en produits de facteurs premiers 2Identifier les facteurs communs 3ConclurePar la méthode de l'algorithme d'Euclide
L'algorithme d'Euclide permet de déterminer le PGCD par divisions successives.
Déterminer le PGCD de 214 et de 32.
Poser la division euclidienne du plus grand des deux entiers par le plus petit
On pose la division euclidienne du plus grand des deux entiers par le plus petit.
On pose la division euclidienne de 214 par 32 :
214 = \textcolor{Blue}{32} \times 6 + \textcolor{Blue}{22}
Poser les divisions successives des diviseurs par les restes
Si le reste de la précédente division euclidienne n'est pas nul, on pose une nouvelle division euclidienne : celle du diviseur par le reste de la précédente division euclidienne.
Tant que le reste n'est pas nul, on réitère la division du diviseur par le reste.
Veiller à ne pas mélanger les diviseurs et les restes.
Le reste n'étant pas nul, on pose la division euclidienne de 32 par 22 :
32= \textcolor{Blue}{22} \times 1 + \textcolor{Blue}{10}
Le reste n'étant pas nul, on pose la division euclidienne de 22 par 10 :
22= \textcolor{Blue}{10} \times 2 + \textcolor{Blue}{2}
Le reste n'étant pas nul, on pose la division euclidienne de 10 par 2 :
10= \textcolor{Blue}{2} \times 5 + \textcolor{Blue}{0}
Le reste étant nul, on arrête l'algorithme.
Identifier le dernier reste non nul
Dès que l'on obtient une division euclidienne de reste nul, on identifie le reste (non nul) de la division euclidienne précédente : ce nombre est le PGCD des deux entiers initiaux.
L'avant-dernière division euclidienne est :
22= 10\times 2 + \textcolor{Green}{2}
On en conclut que :
PGCD \left(214 ;32\right) = 2
Par la méthode des soustractions successives
L'algorithme des soustractions successives permet également de déterminer le PGCD de deux entiers.
Déterminer le PGCD de 243 et de 165.
Poser la différence du plus grand nombre par le plus petit
On pose la différence du plus grand nombre par le plus petit.
On pose la différence de 243 et de 165 :
243 -165 = 78
Poser les soustractions successives
On pose les soustractions successives du résultat obtenu par le plus petit des deux termes de la soustraction précédente. On veille toujours à faire la soustraction du terme le plus grand par le terme le plus petit afin d'avoir un résultat positif.
On réitère la soustraction tant que le résultat n'est pas nul.
Comme le résultat précédent n'est pas nul, on pose la soustraction de 165 par 78 :
165-78 = 87
Comme le résultat précédent n'est pas nul, on pose la soustraction de 87 par 78 :
87-78 = 9
On continue ainsi jusqu'à obtenir un résultat nul :
78-9 = 69
69-9=60
60-9 =51
51-9=42
42-9 = 33
33-9=24
24-9 = 15
15-9 =6
9-6 = 3
6-3=3
3-3=0
Identifier le dernier résultat non nul
Dès que l'on obtient une soustraction de résultat nul, on identifie le résultat (non nul) de la soustraction précédente : ce nombre est le PGCD des deux entiers initiaux.
L'avant-dernière soustraction est :
6-3 = 3
On en conclut que :
PGCD \left(243 ; 165\right) = 3
La méthode de recherche du PGCD à l'aide des soustractions successives est beaucoup plus longue que celle faisant appel à l'algorithme d'Euclide, on préférera donc cette dernière.
A l'aide de PGCD \left(k\times a ; k \times b\right) = k \times PGCD \left(a;b\right)
Afin de déterminer un PGCD, on peut utiliser la propriété suivante :
PGCD \left(k\times a ; k \times b\right) = k \times PGCD \left(a;b\right).
Déterminer le PGCD de 170 et de 130.
Déterminer le diviseur commun
On détermine un diviseur commun aux deux nombres.
On remarque que 170 et 130 sont divisibles par 10.
Réciter le cours
On rappelle que :
PGCD \left(k\times a ; k \times b\right) = k\times PGCD \left(a;b\right), avec a, b et k des entiers
On sait que :
PGCD \left(k\times a ; k \times b\right) = k\times PGCD \left(a;b\right), avec a, b et k des entiers
Conclure
On conclut en donnant le PGCD des deux nombres.
On en déduit que :
PGCD \left(170 ; 130\right) = PGCD \left(10 \times 17 ; 10 \times 13\right)
\Leftrightarrow PGCD \left(170 ; 130\right) = 10 \times PGCD \left(17 ; 13\right)
Or les nombres 17 et 13 sont premiers entre eux.
On en conclut que :
PGCD \left(170 ; 130\right) = 10
Par la décomposition en facteurs premiers
Afin de déterminer le PGCD de deux nombres, on peut les décomposer en produits de facteurs premiers, le PGCD est alors égal au produit des facteurs premiers communs aux deux nombres.
Déterminer le PGCD de 1638 et de 8316.
Décomposer les deux nombres en produits de facteurs premiers
On décompose les deux nombres en produits de facteurs premiers.
On décompose 1638 en produit de facteurs premiers :
1\ 638 = 2\times 819
819=3\times 273
273 = 3 \times 91
91 = 7 \times 13
On en déduit que :
1\ 638 = 2\times 3^2\times 7 \times 13
On décompose ensuite 8316 en produit de facteurs premiers :
8\ 316= 2\times 4\ 158
4\ 158=2\times 2\ 079
2\ 079= 3 \times 693
693= 3 \times 231
231 = 3 \times 77
77 = 7 \times 11
On en déduit que :
8\ 316= 2^2\times 3^3\times 7 \times 11
Identifier les facteurs communs
On identifie le produit de facteurs premiers commun aux deux nombres.
On remarque que 1638 et 8316 ont pour facteur commun 2 \times 3^2 \times 7.
Conclure
Le PGCD des deux nombres est ainsi le produit des facteurs premiers communs à ces deux nombres.
On en déduit que :
PGCD\left(8\ 316; 1\ 638\right) = 2\times 3^2 \times 7
Soit :
PGCD \left(8\ 316;1\ 638\right) = 126