Algoritmo de Euclides extendido

Mientras que el algoritmo de Euclides calcula únicamente el máximo común divisor (GCD) de dos enteros no negativos $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 = \gcd(a, b)$

Es importante notar que, por la identidad de Bézout , siempre podemos encontrar tal representación. Por ejemplo, $\gcd(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 diofánticas lineales. Ese artículo se apoyará en este algoritmo.

Algoritmo

Denotaremos el GCD de $a$ y $b$ con $g$ en esta sección.

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

Partiendo de estos coeficientes $(x, y) = (1, 0)$ , podemos ir hacia atrás por las llamadas recursivas. Todo lo que necesitamos es determinar 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$

Sustituir esta expresión en la ecuación de coeficientes 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, después de reordenar los términos:

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

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

${\begin{cases} x = y_{1} \\ y = x_{1} - y_{1} \cdot ⌊ \frac{a}{b} ⌋ \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 de arriba devuelve el GCD y los valores de los coeficientes en x e y (que se pasan a la función por referencia).

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

Versión iterativa

También es posible escribir el algoritmo de Euclides extendido de forma iterativa. Como evita la recursión, el código se ejecutará un poco más rápido que la versión recursiva.


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 observamos con atención las variables a1 y b1, podemos notar que toman exactamente los mismos valores que en la versión iterativa del algoritmo de Euclides normal. Así que el algoritmo al menos calculará el GCD correcto.

Para ver por qué el algoritmo calcula los coeficientes correctos, consideremos que los siguientes invariantes se cumplen en todo momento (antes de que comience el bucle while y al final de cada iteración):

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

$x_1 \cdot a + y_1 \cdot b = b_1$

Denotemos los valores al final de una iteración con una prima ( $’$ ), y supongamos $q = \frac{a_1}{b_1}$ . Del algoritmo de Euclides, tenemos:

$a_1’ = b_1$

$b_1’ = a_1 - q \cdot b_1$

Para que se cumpla el primer invariante, debe valer lo siguiente:

$x’ \cdot a + y’ \cdot b = a_1’ = b_1$

$x’ \cdot a + y’ \cdot b = x_1 \cdot a + y_1 \cdot b$

De forma análoga, para el segundo invariante debe valer:

$x_1’ \cdot a + y_1’ \cdot b = a_1 - q \cdot b_1$

$x_1’ \cdot a + y_1’ \cdot b = (x - q \cdot x_1) \cdot a + (y - q \cdot y_1) \cdot b$

Comparando los coeficientes de $a$ y $b$ se pueden derivar las ecuaciones de actualización de cada variable, lo que garantiza que los invariantes se mantienen a lo largo del algoritmo.

Al final sabemos que $a_1$ contiene el GCD, así que $x \cdot a + y \cdot b = g$ . Eso significa que encontramos los coeficientes pedidos.

Incluso se puede optimizar más el código y quitar las variables $a_1$ y $b_1$ , y reutilizar simplemente $a$ y $b$ . Sin embargo, si se hace eso, se pierde la capacidad de razonar sobre los invariantes.

Algoritmo de Euclides extendido

Algoritmo

Implementación

Versión iterativa

Problemas de práctica