Nous allons voir dans ce cours le PGCD et Algorithme d’ Euclide ( division successives ) à l’aide de plusieurs exemples détaillés.
Contenu
PGCD : Plus Grand Commun Diviseur :
Rappel sur le PGCD :
PGCD de deux nombres est le plus grand diviseur commun à ces deux nombres :
P = Plus , G = Grand , C = Commun et D = Diviseur
Pour le trouver, on peut écrire la liste des diviseurs du premier nombre, la liste des diviseurs du deuxième, et chercher le plus grand diviseur commun aux deux listes.
Exemples : Déterminer le PGCD entre deux nombres :
Exemple 1 :
Prenons les deux nombres 6 et 9 :
- Les diviseurs de 6 sont : 6 ; 3 ; 2 et 1
- Les diviseurs de 9 sont : 9 ; 3 et 1
Les diviseurs communs entre les diviseurs de 6 et 9 sont : 3 et 1.
On remarque que le plus grand diviseur commun entre les diviseurs de 6 et 9 est 3 et on écrit :
PGCD ( 6 ; 9 ) = 3
Exemple 2 :
Prenons les deux nombres 8 et 14 :
- Les diviseurs de 8 sont : 8 ; 4 ; 2 et 1
- Les diviseurs de 14 sont : 14 ; 7 ; 2 et 1
Les diviseurs communs entre les diviseurs de 8 et 14 sont : 2 et 1.
On remarque que le plus grand diviseur commun entre les diviseurs de 8 et 14 est 2 et on écrit :
PGCD ( 8 ; 14 ) = 2
Exemple 3 :
Prenons les deux nombres 16 et 32 :
- Les diviseurs de 16 sont : 16 ; 8 ; 4 ; 2 et 1
- Les diviseurs de 32 sont : 32 ; 16 ; 8 ; 4 ; 2 et 1
Les diviseurs communs entre les diviseurs de 16 et 32 sont : 16 ; 8 ; 4 ; 2 et 1.
Le plus grand diviseur commun est : 16
PGCD ( 8 ; 14 ) = 16
PGCD et Algorithme d’ Euclide :
Définition :
L’algorithme d’Euclide ou les divisions successives, permet de déterminer le plus grand commun diviseur (PGCD) de deux nombres entiers sans connaître leur factorisation.
L’Algorithme d’Euclide, nous permet aussi de démontrer si deux nombres sont premiers entre eux (ou non).
PGCD et Algorithme d’ Euclide ( Exemples ) :
Cet algorithme est expliqué ci-dessous, par 3 exemples ( le troisième exemple présente le cas de deux nombres premiers entre eux : PGCD = 1 ) :
Exemple 1 : Le PGCD de 75 et 40 ?
Solution :
75 = 40 x 1 + 35 ( On divise 75 par 40 )
40 = 35 x 1 + 5 ( On divise 40 par 5 )
35 = 5 x 7 + 0 ( On divise 35 par 7 )
On arrête les divisions, puisque on a eu un reste Nul. Donc le PGCD est le reste trouvé juste avant 0. C’est-à-dire 5 et on écrit :
PGCD (75 ; 40) = 5( On divise 9 par 3 et on arrête les divisions puisque le reste = 0 )
Exemple 2 : Le PGCD de 87 et 33 ?
Solution :
87 = 33 x 2 + 21 ( On divise 87 par 33 )
33 = 21 x 1 + 12 ( On divise 33 par 21 )
21 = 12 x 1 + 9 ( On divise 21 par 12 )
12 = 9 x 1 + 3 ( On divise 12 par 9 )
9 = 3 x 3 + 0
Donc, PGCD( 87 ; 33) = 3
Exemple 3 : Le PGCD de 57 et 23 ?
( Cas de deux nombres premiers entre eux )
Solution :
57 = 23 x 2 + 11 ( On divise 57 par 23 )
23 = 11 x 2 + 1 ( On divise 23 par 11 et on arrête les divisions car le reste = 1 )
Donc, PGCD (57 ; 23) = 1
On dit que 57 et 23 sont deux nombres premiers entre eux.
Autres lien utiles :
Si ce n’est pas encore clair pour toi ou tu as des questions sur le calcul du PGCD et Algorithme d’ Euclide, n’hésite surtout pas de laisser un commentaire en bas et nous te répondrons le plutôt possible :).
Sinon, écris le mot qui te passe à la tête
