Quand on fait la division euclidienne du polynôme A par le polynôme B, on trouve , donc le PGCD des polynômes et est égal au PGCD des polynômes et .

On continue par la division de par , et on recommence le même procédé jusqu'à l'obtention d'un reste nul.