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.