Chapitres
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 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 |
Vous avez aimé cet article ? Notez-le !
Loading...
Si vous désirez une aide personnalisée, contactez dès maintenant l’un de nos professeurs !
super cours c’est trés utile, merci
Bonjour, merci à vous pour votre fidélité !
Bonne journée !
Bonjours je souhaiterai sa le procédé qu’il faut faire pour obtenir ces resultat avec la calculatrice
Merci