12.2 Algorithme d’Euclide

Pour déterminer le pgcd de deux nombres, on peut utiliser une méthode appelée algorithme d’Euclide : (Ici, on ne démontrera pas la validité de cet algorithme)

Voici le principe : Étant donnés deux entiers positifs a et b, on commence par tester si b est nul. Si oui, alors le PGCD est égal à a. Sinon, on calcule r, le reste de la division de a par b. On remplace a par b, puis b par r, et on recommence le procédé.
Calculons par exemple, le pgcd de 2160 et 888 par cet algorithme avec les étapes suivantes :

Le pgcd de 2160 et 888 est donc 24. Il n’y pas de plus grand entier qui divise ces deux nombres. (En fait 2160 = 24 × 90 et 888 = 24 × 37)
Le pgcd est en fait le dernier reste non nul.