1 - Méthode des soustractions successives
Cette méthode se base sur le résultat suivant :
Théorème
Soient et sont deux entiers naturels non nuls avec alors .
Remarque
L'intérêt de ce théorème est qu'il remplace le calcul du PGCD de deux nombres par le calcul du PGCD de deux nombres plus petits. On peut ainsi calculer un PGCD utilisant plusieurs fois de suite ce théorème (méthode des soustractions successives).
Exemple
Calculons le PGCD de et par la méthode des soustractions successives.
donc
donc
donc
donc
donc
donc
donc
donc
donc
donc
donc
donc
Or évidemment donc finalement :
.
Remarque
On voit que cette méthode est assez simple au niveau calcul (elle ne requiert que des soustractions) mais elle peut dans certains cas s'avérer assez longue. Une méthode plus rapide est l'algorithme d'Euclide.
2 - Algorithme d'Euclide
L'algorithme d'Euclide utilise le théorème suivant :
Théorème
Soient et sont deux entiers naturels non nuls avec et le reste de la division euclidienne de par .
Si alors .
Remarques
Si , cela signifie que divise donc dans ce cas
Comme le précédent, ce théorème remplace le calcul d'un PGCD par le calcul du PGCD de deux nombres plus petits.
On peut, là encore, calculer un PGCD utilisant plusieurs fois de suite ce théorème. cette méthode s'appelle l'algorithme d'Euclide (ou la méthode des divisions successives).
Exemple
Calculons, à nouveau, le PGCD de et mais avec l'algorithme d'Euclide cette fois :
: et donc
: et donc
: et donc
: et
On s'arrête car le reste est nul.
Le PGCD est le dernier reste non nul donc :
.
Remarque
Si vous souhaitez vous entraîner à cette méthode, vous pouvez vérifier votre calcul et votre résultat grâce à cet outil : PGCD Algorithme d'Euclide