Définition

Le Plus Grand Diviseur Commun à plusieurs nombres est appelé PGCD de ces nombres.

Exemple : Trouver le PGCD de 12 et 18. 1 ; 12 ; 2 ; 6 ; 3 ; 4                                                         1 ; 18 ; 2 ; 9 ; 3 ; 6 Donc PGCd de (12 ; 18) = 6. Si les nombres ne sont pas très grands, la méthode précédente convient, mais pour des nombres très grands, cela devient très long.

Algorithme d'Euclide (Mathématicien grec du 3è s. av. JC)

Exemple : Déterminer le PGCD de 31 929 et 15 047. 31 929 et 15 047 sont grands : il est donc difficile de trouver à l'aide des règles de divisibilité tous leurs diviseurs communs et leur PGCD. On applique alors l'algorithme dit d'Euclide qui consiste à écrire une série de divisions euclidiennes.

Méthode

L'algorithme d'Euclide donne :
On écrit l'égalité correspondant à la division euclidienne de 31 929 par 15 04731 929 = 2 x 15 047 + 1835
On effectue la division euclidienne du dernier diviseur 15 047 par le dernier reste 183515 047 = 8 x 1835 + 367
On recommende le procédé : on effectue la division du dernier diviseur 1 835 par le dernier reste 3671 835 = 5 x 367 + 7
L'algorithme s'arrête : on conclut Le PGCD est le dernier reste non nulLe PGCD de 31 929 et           15 047 est 367

Algorithme des différences

On peut utiliser aussi l'algorithme des différence qui consiste à écrire une suite de soustractions :

MéthodeL'algorithme des soustractions donne
On                          soustrait le plus petit des deux nombres au plus grand31 929 - 15 047 = 16 882
On grade les deux plus petit (15 047 et 16 882). Et on soustrait le plus petit des deux nouveaux nombres au plus grand16 882 - 15 047 = 1835
On recommence le procédé : on garde les deux plus petits nombres et on soustrait le plus petit des deux au plus grand
L'algorithme s'arrête lorsque l'on trouve un résultat nuk. On conclut. Le PGCD est le dernier résultat non nul.PGCD (31 929 ; 15 047) = 367

Vous avez aimé l’article ?

Aucune information ? Sérieusement ?Ok, nous tacherons de faire mieux pour le prochainLa moyenne, ouf ! Pas mieux ?Merci. Posez vos questions dans les commentaires.Un plaisir de vous aider ! :) (5,00/ 5 pour 1 votes)
Loading...

Olivier

Professeur en lycée et classe prépa, je vous livre ici quelques conseils utiles à travers mes cours !

Vous avez aimé
cette ressource ?

Bravo !

Téléchargez-là au format pdf en ajoutant simplement votre e-mail !

{{ downloadEmailSaved }}

Votre email est invalide