On effectue des divisions euclidiennes successives et le PGCD est le dernier reste non nul à une constante multiplicative près.

Dans l'algorithme de détermination d'un couple vérifiant l'identité où est le PGCD de et , on donne, dans chaque division euclidienne, l'expression du reste en fonction d'abord des polynômes ' dividende ' et ' diviseur ' pour pouvoir les écrire ensuite en fonction des deux polynômes dont on cherche le PGCD.