PGCD

1 Définition

           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 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.

2. Le calcul du PGCD

2.1. Décomposition en facteurs premiers.

Pour déterminer le pgcd de deux nombres a et b, on décompose a 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.    Calculer le PGCD(48,32)

2.    Calculer le PGCD(168,80)

 

Solution

 

1. Décomposer en produit des facteurs premiers les nombres 48 et 32, puis en déduire leur PGCD.

48=2⁴x3

32=2⁵

PGCD (48 ; 32)=2⁴=16       // 2 est commun aux deux décompositions, on retient le 2 qui a le plus petit exposant(2³)

 

2. Décomposer en produit des facteurs premiers les nombres 168 et 120, puis en déduire leur PGCD.

168=2x2x2x3x7=2³x3x7

80=2x2x2x2x5=2⁴x5

 PGCD(168,80)= 2³=8

 

 

2.2. 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.

2.3. 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.

3. Relation entre le PPCM et le PGCD de deux entiers naturels

Si a et b sont deux entiers naturels non nuls, alors PPMC (a, b )=

 

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 :

RESOLUTIONS

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 =2²x3²x1

 

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 :