Tout d'abord qu'est-ce que le PGCD ?

Eh bien c'est le Plus Grand Commun Diviseur, le plus grand diviseur commun à 2 nombres a et b.

Exemple :

On cherche le PGCD de 10 et 20

Diviseurs de 20 : 1 ; 20 ; 5 ; 4 ; 2 ; 10

Diviseurs de 10 : 1 ; 10 ; 5 ; 2

Quels sont les diviseurs commun ?

1 ; 2 ; 5 et 10

Lequel est le plus grand ?

10

On a donc PGCD (20 ; 10) = 10

Seulement, rechercher tous les diviseurs de nombres comme 224 et 80 peut être pénible et surtout très lent. Heureusement il y a d'autres méthodes.

L'algorithme des soustractions successives :

La propriété qui permet cet algorithme est la suivante :

a et b deux nombres entiers positifs avec a>b

On a alors :  PGCD (a ; b) = PGCD (b ; a-b)

On peut calculer le PGCD avec un tableau.

Exemple :

 On calcule le PGCD de 145 et 58 à l'aide de l'algorithme des soustractions successives.

Le PGCD est la dernière différence non-nulle du tableau.

Donc PGCD (145 ; 58) = 29

Attention !!! Dans le tableau a doit toujours être supérieur à b !!!

L'algorithme d'Euclide :

La propriété nous permettant d'utiliser l'algorithme d'Euclide est la suivante :

a et b sont des entiers positifs avec a>b.

PGCD (a ; b) = PGCD (b ; r) où r est le reste de la division euclidienne de a par b.

Exemple :

On calcule le PGCD de 224 et 80 à l'aide de l'algorithme d'Euclide.

224 = 80*2+64  On fait la division euclidienne de 224 par 80

80 = 64*1+16   Le diviseur de l'opération précédente devient le dividende et le reste le diviseur

64 = 16*4+0       Même chose que pour la précédente opération.

Le PGCD est le dernier reste non nul.

PGCD (224 ; 80) = 16

Attention !!!! Si vous voulez avoir tous les points vous devez absolument annoncer l'algorithme que vous allez utiliser !!!

J'espère vous avoir aidé; si vous avez des questions posez-les moi dans les commentaires.

Clément C.