În timp ce algoritmul euclidian calculează doar cel mai mare divizor comun (GCD) a două numere întregi și , versiunea extinsă găsește, de asemenea, o modalitate de a reprezenta GCD în termeni de a și b, adică coeficienții x și y pentru care:
Este important de reținut că putem găsi întotdeauna o astfel de reprezentare, de exemplu
Algoritmul
În această secțiune vom nota GCD-ul lui a și b cu g.
Modificările aduse algoritmului original sunt foarte simple. Dacă ne amintim algoritmul, putem vedea că acesta se termină cu
Pornind de la acești coeficienți
Să presupunem că am găsit coeficienții
și dorim să găsim perechea
Putem reprezenta
Înlocuind această expresie în ecuația coeficientului din
și după rearanjarea termenilor:
Am găsit valorile lui x și y:
Implementare
int gcd(int a, int b, int& x, int& y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d; }
Funcția recursivă de mai sus returnează GCD și valorile coeficienților pentru x și y (care sunt transmise prin referință la funcție).
Această implementare a algoritmului euclidian extins produce rezultate corecte și pentru numere întregi negative.