Î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:

\( a \cdot x + b \cdot y = \gcd(a, b) \)

Este important de reținut că putem găsi întotdeauna o astfel de reprezentare, de exemplu \( \gcd(55, 80) = 5 \) prin urmare, putem reprezenta 5 ca o combinație liniară cu termenii 55 și 80: \( 55 \cdot 3 + 80 \cdot (-2) = 5 \)

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 \( b = 0 \) și \( a=g \). Pentru acești parametri putem găsi cu ușurință coeficienți, și anume \( g\cdot 1 + 0 \cdot 0 = g \).

Pornind de la acești coeficienți \( (x, y) = (1, 0) \), putem merge înapoi în sus în apelurile recursive. Tot ce trebuie să facem este să ne dăm seama cum se schimbă coeficienții și în timpul tranziției de la \( (a, b)) \), la \( (b, a \bmod b) \) .

Să presupunem că am găsit coeficienții \((x_1, y_1) \) pentru \((b, a \bmod b) \):

\(b \cdot x_1 + (a \bmod b) \cdot y_1 = g \)

și dorim să găsim perechea \((x, y) \) pentru \((a, b) \) :

\(a \cdot x + b \cdot y = g \)

Putem reprezenta \(a \bmod b\) sub forma:

\(a \bmod b = a – \left\lfloor \frac{a}{b} \right\rfloor \cdot b\)

Înlocuind această expresie în ecuația coeficientului din \((x_1, y_1)\) se obține:

\(g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + \left(a – \left\lfloor \frac{a}{b} \right\rfloor \cdot b \right) \cdot y_1)\)

și după rearanjarea termenilor:

\(g = a \cdot y_1 + b \cdot \left( x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor \right)\)

Am găsit valorile lui x și y:

\(\begin{cases}
x = y_1 \\
y = x_1 – y_1 \cdot \left\lfloor \frac{a}{b} \right\rfloor
\end{cases}\)

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.