L'algorithme est basé sur les deux résultats suivants :
Si A est un entier alors PGCD(A,0)=A
Si A et B sont deux entiers (avec A>B) et si R est le reste de la division euclidienne de A par B alors PGCD(A,B)=PGCD(B,R)
(c'est pour cela que dans l'algorithme, A prend la valeur de B et B prend la valeur de R : le processus peut ainsi se poursuivre)
On procède par division euclidienne successive jusqu'à obtenir un reste nul.
Exemple :
PGCD(1071,1029)
=PGCD(1029,42) car 1071=1029*1+42
=PGCD(42,21) car 1029=42*24+21
=PGCD(21,0) car 42=21*2+0
=21