- PGCD DE DEUX NOMBRES ENTIERS NATURELS
- Qu’est-ce que le PGCD
PGCD signifie plus grand commun diviseur. Le PGCD de deux nombres entiers naturels a et b est le plus grand des nombres entiers naturels qui divisent a et b à la fois. On la note PGCD (a ; b)
Exemple :
La liste des nombres entiers naturels qui divisent 16 et 24 est constituée de 1 ; 2 ; 4 ; 8 et le plus grand d’entre eux est 8 on dit alors que le PGCD (16 ; 24)=8
Propriété :
PGCD (a; b)=PGCD (b; a)
- Comment déterminer le PGCD
Pour déterminer le pgcd de deux nombres entiers naturels nous disposons de deux algorithmes : l’algorithme de la soustraction successive et l’algorithme d’Euclide.
- L’algorithme de la soustraction successive
Cet algorithme découle de la propriété suivante :
Propriété
Soit a et b deux nombres entiers naturels :
Si a >b alors PGCD (a ; b) = PGCD (a-b, a)
Exemple :
Déterminons par l’algorithme de la soustraction successive le pgcd de 38 et 10
Posons a=38 et b=10
L’algorithme se déroule comme suit :
A
|
38
|
28
|
18
|
10
|
8
|
6
|
4
|
2
|
B
|
10
|
10
|
10
|
8
|
2
|
2
|
2
|
2
|
a-b
|
28
|
18
|
8
|
2
|
6
|
4
|
2
|
0
|
On s’arrête lorsque a=b et dans le tableau ci-dessus on a :
a =2 =b donc, PGCD (38 ; 10)=2
- L’algorithme d’Euclide
Soient a et b deux nombres entiers naturels tels que b≠0
Effectuer la division euclidienne de a par b c’est déterminer le quotient Q et le reste R de la division de a par b
On a alors : a=b×q+r
L’algorithme d’Euclide s’applique sur les propriétés suivantes :
Propriété :
Soit r le reste de la division euclidienne de a par b. Où a et b sont deux entiers naturels tels que b soit non nul.
- Si r= 0 alors PGCD (a, b) = b
- Si r ≠ 0 alors PGCD (a, b) = PGCD (b, r) c’est –à– dire
PGCD (dividende, diviseur) = PGCD (diviseur, reste)
Exemple :
Déterminer par l’algorithme d’Euclide le pgcd de 298 et 70
L’algorithme se déroule comme suit :
Dividende (a)
|
298
|
70
|
18
|
16
|
Diviseur (b)
|
70
|
18
|
16
|
2
|
Reste (r)
|
18
|
16
|
2
|
0
|
Le pgcd est le dernier reste non nul. Donc PGCD(298,70)= 2