Embora o algoritmo Euclidiano calcule apenas o maior divisor comum (GCD) de dois inteiros $a$ e $b$, a versão estendida também encontra uma forma de representar o GCD em termos de $a$ e $b$, ou seja coeficientes $x$ e $y$ para os quais:

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

É importante notar que podemos sempre encontrar tal representação, por exemplo $\gcd(55, 80) = 5$ portanto podemos representar $5$ como uma combinação linear com os termos $55$ e $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

Uma forma mais geral desse problema é discutida no artigo sobre Equações Diofantinas Lineares.Ele será construído sobre este algoritmo.

Algoritmo

Denotaremos o GCD de $a$ e $b$ com $g$ nesta seção.

As alterações ao algoritmo original são muito simples. Se nos lembrarmos do algoritmo, podemos ver que o algoritmo termina com $b = 0$ e $a = g$.Para estes parâmetros podemos facilmente encontrar coeficientes, nomeadamente $g \cdot 1 + 0 \cdot 0 = g$.

Iniciando a partir destes coeficientes $(x, y) = (1, 0)$, podemos voltar a subir as chamadas recursivas.Tudo o que precisamos fazer é descobrir como os coeficientes $x$ e $y$ mudam durante a transição de $(a, b)$ para $(b, a \bmod b)$.

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

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

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

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

Podemos representar $a \bmod b$ como:

$$$ a \bmod b = a – piso esquerdo \frac{a}{b} \direita: rfloor {{cdot b$$

Substituindo esta expressão na equação do coeficiente de $(x_1, y_1)$ dá:

$$$ g = b \cdot x_1 + (a \bmod b) \cdot y_1 = b \cdot x_1 + esquerda(a – esquerda do chão delfacto \frac{a}{b} {direita do chão delfacto \cdot b{direita) \cdot y_1$

e depois de rearranjar os termos:

$$$g = a {\i1}a {\i}cdot y_1 + b {\i1}cdot {\i}esquerda( x_1 – y_1 {\i}cdot {\i}esquerda}door piso de frente {\i}{a}{b}direita{\i}rfrac{\i}$

Encontrámos os valores de $x$ e $y$:

$$$begin{cases}x = y_1 {y = x_1 – y_1 {cdot {a}andar esquerdo do chão delfacto {b} \rfloor\end{cases} $$

Implementação

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;}

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

Esta implementação do algoritmo Euclidean estendido produz resultados corretos para inteiros negativos também.

Versão iterativa

Também é possível escrever o algoritmo Euclidiano Estendido de forma iterativa. Como ele evita a recorrência, o código será executado um pouco mais rápido que o recursivo.

int gcd(int a, int b, int& x, int& y) { x = 1, y = 0; int x1 = 0, y1 = 1, a1 = a, b1 = b; while (b1) { int q = a1 / b1; tie(x, x1) = make_tuple(x1, x - q * x1); tie(y, y1) = make_tuple(y1, y - q * y1); tie(a1, b1) = make_tuple(b1, a1 - q * b1); } return a1;}

Se você olhar atentamente para a variável a1 e b1, você pode notar que eles tomam exatamente os mesmos valores que na versão iterativa do algoritmo Euclidiano normal. Assim o algoritmo irá pelo menos calcular o GCD.

Para ver porque é que o algoritmo também calcula os coeficientes correctos, pode verificar que as seguintes invariantes se mantêm a qualquer momento (antes do laço while, e no fim de cada iteração): $x \cdot a + y \cdot b = a_1$ e $x_1 \cdot a + y_1 \cdot b = b_1$.É trivial ver, que estas duas equações estão satisfeitas no início. E você pode verificar se a atualização na iteração do loop ainda manterá essas igualdades válidas.

No final sabemos que $a_1$ contém o GCD, então $x \cdot a + y \cdot b = g$.O que significa que encontramos os coeficientes necessários.

Você pode até otimizar mais o código, e remover a variável $a_1$ e $b_1$ do código, e apenas reutilizar $a$ e $b$.Entretanto, se você fizer isso, você perde a capacidade de discutir sobre os invariantes.

Problemas de prática

• 10104 – Problema Euclides
• GYM – (J) Once Upon A Time
• UVA – 12775 – Gift Dilemma