Mientras que el algoritmo euclidiano calcula sólo el máximo común divisor (GCD) de dos enteros $a$ y $b$, la versión extendida también encuentra una forma de representar el GCD en términos de $a$ y $b$, es decir coeficientes $x$ e $y$ para los cuales:

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

Es importante señalar, que siempre podemos encontrar una representación de este tipo, por ejemplo $\cd(55, 80) = 5$ por lo tanto podemos representar $5$ como una combinación lineal con los términos $55$ y $80$: $55 \cdot 3 + 80 \cdot (-2) = 5$

Una forma más general de ese problema se discute en el artículo sobre Ecuaciones Diofantinas Lineales.Se basará en este algoritmo.

Algoritmo

En esta sección denotaremos el GCD de $a$ y $b$ con $g$.

Los cambios en el algoritmo original son muy sencillos.Si recordamos el algoritmo, podemos ver que el algoritmo termina con $b = 0$ y $a = g$.Para estos parámetros podemos encontrar fácilmente los coeficientes, a saber $g \cdot 1 + 0 \cdot 0 = g$.

A partir de estos coeficientes $(x, y) = (1, 0)$, podemos ir hacia atrás en las llamadas recursivas.Todo lo que tenemos que hacer es averiguar cómo cambian los coeficientes $x$ e $y$ durante la transición de $(a, b)$ a $(b, a \bmod b)$.

Supongamos que encontramos los coeficientes $(x_1, y_1)$ para $(b, a \bmod b)$:

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

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

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

Podemos representar $a \bmod b$ como:

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

Sustituyendo esta expresión en la ecuación del coeficiente de $(x_1, y_1)$ da:

$$ 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$$

y tras reordenar los términos:

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

Hallamos los valores de $x$ e $y$:

$$\Ncomienza{casos}x = y_1 \Ny = x_1 – y_1 \cdot \lfloor \frac{a}{b} \right\rfloor\end{cases} $$

Implementación

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

La función recursiva anterior devuelve el GCD y los valores de los coeficientes a x y y (que se pasan por referencia a la función).

Esta implementación del algoritmo euclidiano extendido produce resultados correctos también para enteros negativos.

Versión iterativa

También es posible escribir el algoritmo euclidiano extendido de forma iterativa.Debido a que se evita la recursión, el código se ejecutará un poco más rápido que el 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;}

Si te fijas bien en las variables a1 y b1, puedes observar que toman exactamente los mismos valores que en la versión iterativa del algoritmo euclidiano normal. Así que el algoritmo calculará al menos el GCD correcto.

Para ver por qué el algoritmo también calcula los coeficientes correctos, puedes comprobar que los siguientes invariantes se mantienen en cualquier momento (antes del bucle while, y al final de cada iteración): $x \cdot a + y \cdot b = a_1$ y $x_1 \cdot a + y_1 \cdot b = b_1$.Es trivial ver, que estas dos ecuaciones se satisfacen al principio.Y se puede comprobar que la actualización en la iteración del bucle seguirá manteniendo esas igualdades válidas.

Al final sabemos que $a_1$ contiene el GCD, por lo que $x \cdot a + y \cdot b = g$.Lo que significa que hemos encontrado los coeficientes necesarios.

Incluso puedes optimizar más el código, y eliminar la variable $a_1$ y $b_1$ del código, y sólo reutilizar $a$ y $b$.Sin embargo, si lo haces, pierdes la capacidad de argumentar sobre los invariantes.

Problemas de práctica

• 10104 – Problema de Euclides
• GYM – (J) Érase una vez
• UVA – 12775 – Dilema del regalo