Algoritmo de Euclides Estendido

Enquanto o Algoritmo de Euclides calcula apenas o maior divisor comum (GCD/MDC) de dois números inteiros $a$ e $b$, a versão estendida também encontra uma maneira de representar o MDC em termos de $a$ e $b$, ou seja, coeficientes $x$ e $y$ para os quais:

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

Algoritmo

As alterações no algoritmo original são muito simples. Tudo o que precisamos fazer é descobrir como os coeficientes $x$ e $y$ mudam durante a transição de $(a, b)$ para $(b \bmod a, a)$.

Vamos supor que encontramos os coeficientes $(x_1, y_1)$ para $(b \bmod a, a)$:

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

e queremos encontrar o par $(x, y)$ para $(a, b)$:

$$ a \cdot x + b \cdot y = g$$

Podemos representar $b \bmod a$ como:

$$ b \bmod a = b - \left\lfloor \frac{b}{a} \right\rfloor \cdot a$$

Substituindo esta expressão na equação do coeficiente de $(x_1, y_1)$ obtém-se:

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

e depois de reorganizar os termos:

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

Encontramos os valores $x$ e $y$:

$$\begin{cases} x = y_1 - \left\lfloor \frac{b}{a} \right\rfloor \cdot x_1 \cr y = x_1 \end{cases} $$

Implementação

int gcd(int a, int b, int & x, int & y) {
    if (a == 0) {
        x = 0;
        y = 1;
        return b;
    }
    int x1, y1;
    int d = gcd(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return d;
}

A função recursiva acima retorna o GCD e os valores dos coeficientes para x and y (que são passados ​​por referência à função).

O caso base da recursão é $a = 0$, quando o GCD é igual a $b$, então os coeficientes $x$ e $y$ são $0$ e $1$, respectivamente. Em todos os outros casos, as fórmulas acima são usadas para recalcular os coeficientes em cada iteração.

Esta implementação do algoritmo de euclides também produz resultados corretos para números inteiros negativos.

Problemas