Cet algorithme repose sur l'itération de la propriété suivante:
Le PGCD de deux nombres a et b, avec a>b, est inchangé si l'on remplace a par a-b .Ainsi,par exemple,on peut remplacer 252 et 105 par 147 et 105 puis par 105 et 42 ;63 et 42;42 et 21; 21 et 21 : Le PGCD de 252 et 105 est donc 21 .