<

Cours de Math 3eme

Les Arithmetiques

Pgcd de deux nombres entiers naturels
  1. PGCD DE DEUX NOMBRES ENTIERS NATURELS

 

 

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

 

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

 

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

 

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

 

 

 

 

 

 

 

par Epie Epie