Dans l'algorithme d'Euclide, on fait des divisions successives et le PGCD est le dernier reste non nul à une constante multiplicative près.