DEFINITION
Soient des nombres entiers naturels non nuls.
· On dit que
d est un diviseur commun de a et b si d est un
diviseur de a et en même temps un diviseur de b.
· On appelle plus
grand commun diviseur de a et b on note PGCD (a, b) le plus grand entier des
diviseurs communs de a et b.
Exemple :
Diviseurs de 12 :1,2,3,4,6
Diviseurs 18 : 1,2,3,6,9
Pgcd (12,18)=6
METHODES DE CALCUL DU PGCD
Décomposition
en facteurs premiers.
Pour déterminer
le pgcd de deux nombres a et b, on décompose a en produits de facteurs premiers et b
en produits de facteurs premiers. Le pgcd s’obtient en prenant les facteurs
communs aux deux décompositions, chacun étant affecté de son plus petit
exposant.
Exemple :
1. Décomposer en produit des facteurs premiers les
nombres 48 et 32, puis en déduire leur PGCD.
48=24x3
32=25
PGCD (48 ; 32)=24=16 // 2 est
commun aux deux décompositions, on retient le 2 qui a le plus petit exposant(23)
2. Décomposer en produit des facteurs premiers les
nombres 168 et 120, puis en déduire leur PGCD.
168=2x2x2x3x7=23x3x7
80=2x2x2x2x5=24x5
PGCD(168,80)=
23=8
Algorithme des soustractions successives
On effectue des
soustractions successives de
a par b. Le PGCD (a, b) est le dernier résultat non nul de a-b .
Exemple : Déterminons le PGCD (168,
120)
168-120=48 ;
120-48=72 ;
72-48=24 ;
48-24=24 ;
24-24=0.
Donc le pgcd
(168,120) est 24
car le résultat de la dernière différence non nulle est 24.
Algorithme d’Euclide
On
effectue les divisions euclidiennes successives de a par b. Le PGCD (a, b) est le dernier
reste non nul. Cet algorithme est
basé sur la propriété suivante :
Si a = bq + r alors PGCD (a, b) = PGCD (b, r)
où r est le reste de la division euclidienne de b par
a, q est le quotient.
Exemple : Déterminons le PGCD
(375,2020)
2020=5x375
+145
375=2x145
+85
145=1x85
+60
85=1x60
+25
60=2x25
+10
25=2x10
+5
10=2x5
+0
le dernier reste non nul des divisions
est 5
donc PGCD (375, 2020) =5
Remarques :
· si b est un diviseur de a, alors PGCD (a. b) = b
· PGCD (a,b) =1
Équivaut à 
est irréductible. On dit que les nombres a et b
sont premiers entre eux.
RELATION
ENTRE LE PPCM ET LE PGCD DE DEUX ENTIERS NATURELS
Si a et b sont deux
entiers naturels non nuls, alors
Exemple:
Déterminer le PPMC de
72 et 30 sachant que
le PGCD est 6
solution : PPMC(72,30)=
=360
EXERCICES
EXERCICE
I :
1. Trouver le reste de la division euclidienne
de 27 par 15.
2. Trouver le reste de la division euclidienne
de 15 par 12.
3. Trouver le reste de la division euclidienne
de 12 par 3.
4. En déduire le plus grand commun diviseur
(PGCD) de 27 et 15.
EXERCICE
II :
1. Décomposer 36 en un produit de facteurs
premiers.
2. Décomposer 30 en un produit de facteurs
premiers.
3. En déduire le plus grand commun diviseur
(PGCD) de 36 et 30.
EXERCICE
III :
1. Calculer les différences successives entre
45 et 35 ; entre 35 et 10 ; entre 25 et 10 ; entre 25 et
15 ; entre 15 et 10 ;
entre 10 et 5 ; entre 5
et 5 .
2. En déduire le plus grand commun diviseur
(pgcd) de 45 et 35.
3. Quelles sont les étapes à suivre
pour réaliser cette tâche.
4. Retrouver à partir du résultat de la
question 2 le PPMC(45,35).
EXERCICE
IV :
Le père d’Abena a le projet de carreler le sol
de son salon de dimensions 462cmx561cm.Il ne voudrait pas découper les
carreaux, ni laisser des espaces entre les carreaux posés au sol. Il fait appel
à sa fille Agnès pour déterminer le nombre minimum de carreaux nécessaires pour
réaliser le projet. Aidez Agnès à déterminer le nombre de carreaux.
EXERCICE
V :
1.On veut recouvrir une surface rectangulaire de 4,75 m
sur 3,61 m avec des dalles carrées dont le côté mesure un nombre entier de
centimètres. Quelle est la taille maximale de ces dalles ?
2.On dispose
d'une feuille de papier. On découpe dans cette feuille le plus grand carré
possible. Dans le morceau restant, on découpe encore le plus grand carré
possible, et ainsi de suite... On continue à découper le plus grand carré
possible jusqu'à ce que le morceau restant soit lui-même un carré. Quelle est
la taille du dernier carré si les dimensions de la feuille initiale sont 192 cm
sur 84 cm ? Même question si les dimensions initiales sont deux entiers
quelconques
CORRIGES
Exercice I :
//si a divisé par b
donne q et le reste est r, on a : a=bxq +r
a est le dividende
b est le diviseur
r est le reste
1. Reste de la division euclidienne de 27
par 15. => 27=15x1 +12
27 :15=1 reste=12
2.
Reste de la division euclidienne de 15 par 12. => 15=12x1 +3
15 :12=1 reste=3
3. Reste de la division euclidienne de 12
par 3=> 12
=3x4 +0
12 :3=4 reste=0
4. Le PGCD est le dernier reste non nul
3. //C’est la
détermination du pgcd par l’algorithme d’Euclide
Exercice II :
1. Décomposer 36 en un produit de facteurs
premiers.
36 2
18 2
9 3
3 3
1
36=2x2x3x3x1 =22x32x1
2. Décomposer 30 en un produit de facteurs
premiers.
30 2
15 3
5 5
1
30=2x3x5x1
3. Le pgcd est issu des facteurs communs aux
deux décompositions, chacun étant affecté de son plus petit exposant.
Pgcd(36,30)=2x3=6
Exercice III :
1.
45-35=10
35-10=25
25-10=15
15-10=5
10-5=5
5-5=0
2. Le pgcd est le dernier résultat non nul
5.
3.
si a=b alors PGCD(a,b) = a
(ou b)
Sinon PGCD(a,b) = PGCD(a-b,b) si a > b
Sinon PGCD(a,b) = PGCD(a, b-a)
4. PPMC (45,35) =
= 315
EXERCICE IV :
Il suffit de trouver PGCD (561,462) =33
EXERCICE V :
1.Il faut
déterminer PGCD(361;475).
On effectue
les divisions euclidiennes successives. Le dernier reste non nul étant 19, le
PGCD de 475 et 361 est 19. non nul puis à l’aide de
dalles carrées de 19 cm de côté, on peut donc carreler une surface
rectangulaire de 4,75 m sur 3,61 m (il faudra 19 dalles en longueur et 25 en
largeur, soit un total de 475 dalles en tout.
2. La
taille du dernier carré sera PGCD(84 ;192)=12 De
manière générale, si on note x et y les dimensions de la feuille initiale, la
taille du dernier carré sera PGCD(x ;y).