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.

Les meilleurs professeurs de Maths disponibles
Greg
5
5 (145 avis)
Greg
100€
/h
Gift icon
1er cours offert !
Nicolas
4,9
4,9 (139 avis)
Nicolas
35€
/h
Gift icon
1er cours offert !
Houssem
5
5 (118 avis)
Houssem
55€
/h
Gift icon
1er cours offert !
Moujib
5
5 (81 avis)
Moujib
75€
/h
Gift icon
1er cours offert !
Antoine
4,9
4,9 (110 avis)
Antoine
60€
/h
Gift icon
1er cours offert !
Sébastien
5
5 (80 avis)
Sébastien
75€
/h
Gift icon
1er cours offert !
Térence
4,9
4,9 (66 avis)
Térence
50€
/h
Gift icon
1er cours offert !
Laurent
4,9
4,9 (96 avis)
Laurent
50€
/h
Gift icon
1er cours offert !
Greg
5
5 (145 avis)
Greg
100€
/h
Gift icon
1er cours offert !
Nicolas
4,9
4,9 (139 avis)
Nicolas
35€
/h
Gift icon
1er cours offert !
Houssem
5
5 (118 avis)
Houssem
55€
/h
Gift icon
1er cours offert !
Moujib
5
5 (81 avis)
Moujib
75€
/h
Gift icon
1er cours offert !
Antoine
4,9
4,9 (110 avis)
Antoine
60€
/h
Gift icon
1er cours offert !
Sébastien
5
5 (80 avis)
Sébastien
75€
/h
Gift icon
1er cours offert !
Térence
4,9
4,9 (66 avis)
Térence
50€
/h
Gift icon
1er cours offert !
Laurent
4,9
4,9 (96 avis)
Laurent
50€
/h
Gift icon
1er cours offert !
C'est parti

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 047 31 929 = 2 x 15 047 + 1835
On effectue la division euclidienne du dernier diviseur 15 047 par le dernier reste 1835 15 047 = 8 x 1835 + 367
On recommende le procédé : on effectue la division du dernier diviseur 1 835 par le dernier reste 367 1 835 = 5 x 367 + 7
L'algorithme s'arrête : on conclut

Le PGCD est le dernier reste non nul

Le 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éthode L'algorithme des soustractions donne
On                          soustrait le plus petit des deux nombres au plus grand 31 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 grand 16 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
>

La plateforme qui connecte profs particuliers et élèves

Vous avez aimé cet article ? Notez-le !

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 (2 note(s))
Loading...

Olivier

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