Si , l'ensemble des diviseurs de a et b est égal à l'ensemble des diviseurs de b et r, par conséquent le pgcd de a et b est égal au pgcd de b et r.

En effectuant des divisions euclidiennes, on calcule les quotients et les restes successifs jusqu'à ce que l'on trouve un reste nul :

On a donc :

Or .

Donc .

Remarques : Le pgcd de 41773 et 19277 est le dernier reste non nul, dans les divisions euclidiennes successives.   et .