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
1er cours offert !
Houssem
5
5 (105 avis)
Houssem
70€
/h
1er cours offert !
Anis
4,9
4,9 (78 avis)
Anis
80€
/h
1er cours offert !
Greg
5
5 (95 avis)
Greg
120€
/h
1er cours offert !
Laurent
4,9
4,9 (86 avis)
Laurent
50€
/h
1er cours offert !
Grégory
5
5 (83 avis)
Grégory
105€
/h
1er cours offert !
Ahmed
4,9
4,9 (78 avis)
Ahmed
40€
/h
1er cours offert !
Jean-charles
5
5 (20 avis)
Jean-charles
20€
/h
1er cours offert !
Pierre-thomas
5
5 (40 avis)
Pierre-thomas
80€
/h
1er cours offert !
Houssem
5
5 (105 avis)
Houssem
70€
/h
1er cours offert !
Anis
4,9
4,9 (78 avis)
Anis
80€
/h
1er cours offert !
Greg
5
5 (95 avis)
Greg
120€
/h
1er cours offert !
Laurent
4,9
4,9 (86 avis)
Laurent
50€
/h
1er cours offert !
Grégory
5
5 (83 avis)
Grégory
105€
/h
1er cours offert !
Ahmed
4,9
4,9 (78 avis)
Ahmed
40€
/h
1er cours offert !
Jean-charles
5
5 (20 avis)
Jean-charles
20€
/h
1er cours offert !
Pierre-thomas
5
5 (40 avis)
Pierre-thomas
80€
/h
1er cours offert>

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
Besoin d'un professeur de Maths ?

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

Olivier

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