le PGCD
|
|
|
 | Définitions |
Un diviseur commun à deux ou plusieurs nombres entiers est un diviseur entier qui divise chacun d'eux.
Exemples :
- 2 est diviseur de 6 et 10
- 3 est diviseur de 12 et 36
2 et diviseur de 10 car 10/2 = 5. On trouve une valeur entière
- les diviseurs de 12 sont 1, 2, 3, 4, 6, et 12.
- les diviseurs de 36 sont 1, 2, 3, 4, 6, 12, 18 et 36.
Le plus grand commun diviseur à deux ou plusieurs nombres est appelé PGCD ( plus grand commun diviseur ).
Exemple :
Le plus grand commun diviseur entre 12 et 36 est 12. Donc PGCD de 12 et 36 est 12.
| Algorithme d'Euclide |
Soient A et B deux nombres entiers.
Exemple : Calculer le PGCD de 1053 et 325.
A=1053 et B=325
|
Étape 1 : On range A et B par ordre croissant |
|
Étape 2 : On effectue la division de 1053 par 325 |
|
Étape 3 : Comme le reste est différent de 0, il faut réitérer la méthode en prenant le reste 78 et en gardant uniquement le diviseur. |
|
Étape 4 : on effectue une nouvelle division 325 par 78 |
|
Étape 5 : Comme le reste est différent de 0, il faut recommencer la méthode en prenant le reste 13 et en gardant uniquement le diviseur soit 78. |
|
Étape 6 : On effectue 78 par 13. |
|
Étape 7 : Le reste est nul, donc le diviseur 13 est le PGCD de 1053 et 325. |
|
Deux nombres sont premiers si le PGCD = 1, c'est à dire qu'il n'existe pas de diviseurs entre les deux nombres. |