¿Cómo utilizar manualmente el Algoritmo Euclidiano Extendido?

Question

Sólo he encontrado un algoritmo recursivo del algoritmo euclidiano extendido. Me gustaría saber cómo utilizarlo a mano. ¿Alguna idea?

Answer 1

Tal vez la forma más fácil de hacerlo a mano sea por analogía con la eliminación gaussiana o la triangularización, excepto que, como el anillo de coeficientes no es un campo, debemos utilizar el algoritmo de división / euclidiano para disminuir iterativamente los coeficientes hasta cero. Para calcular ambos $\rm\,gcd(a,b)\,$ y su representación lineal de Bezout $\rm\,j\,a+k\,b,\,$ mantenemos un registro de tales representaciones lineales para cada resto en el algoritmo euclidiano, comenzando con la representación trivial de los argumentos gcd, por ejemplo $\rm\: a = 1\cdot a + 0\cdot b.\:$ En términos matriciales, esto se consigue aumentando (añadiendo) una matriz de identidad que acumula el efecto de las operaciones de fila elementales. A continuación se muestra un ejemplo que calcula la representación de Bezout para $\rm\:gcd(80,62) = 2,\ $ es decir $\ 7\cdot 80\: -\: 9\cdot 62\ =\ 2\:.\:$ Ver esta respuesta para una demostración y para la motivación conceptual de las ideas que hay detrás del algoritmo (véase la Observación más abajo si no está familiarizado con las operaciones de fila del álgebra lineal).

For example, to solve  m x + n y = gcd(m,n) we begin with
two rows  [m   1    0], [n   0    1], representing the two
equations  m = 1m + 0n,  n = 0m + 1n. Then we execute
the Euclidean algorithm on the numbers in the first column,
doing the same operations in parallel on the other columns.

Here is an example:  d =  x(80) + y(62)  proceeds as:

                      in equation form   | in row form
                    ---------------------+------------
                    80 =   1(80) + 0(62) | 80   1   0
                    62 =   0(80) + 1(62) | 62   0   1
 row1 -   row2  ->  18 =   1(80) - 1(62) | 18   1  -1
 row2 - 3 row3  ->   8 =  -3(80) + 4(62) |  8  -3   4
 row3 - 2 row4  ->   2 =   7(80) - 9(62) |  2   7  -9
 row4 - 4 row5  ->   0 = -31(80) +40(62) |  0 -31  40

The row operations above are those resulting from applying
the Euclidean algorithm to the numbers in the first column,

        row1 row2 row3 row4 row5
namely:  80,  62,  18,   8,   2  = Euclidean remainder sequence
               |    |
for example   62-3(18) = 8, the 2nd step in Euclidean algorithm

becomes:   row2 -3 row3 = row4  when extended to all columns.

In effect we have row-reduced the first two rows to the last two.
The matrix effecting the reduction is in the bottom right corner.
It starts as 1, and is multiplied by each elementary row operation, 
hence it accumulates the product of all the row operations, namely:

$$ \left[ \begin{array}{ccc} 7 & -9\\ -31 & 40\end{array}\right ] \left[ \begin{array}{ccc} 80 & 1 & 0\\ 62 & 0 & 1\end{array}\right ] \ =\ \left[ \begin{array}{ccc} 2\ & \ \ \ 7\ & -9\\ 0\ & -31\ & 40\end{array}\right ] \qquad\qquad\qquad\qquad\qquad $$

Notice row 1 is the particular  solution  2 =   7(80) -  9(62)
Notice row 2 is the homogeneous solution  0 = -31(80) + 40(62),
so the general solution is any linear combination of the two:

       n row1 + m row2  ->  2n = (7n-31m) 80 + (40m-9n) 62

The same row/column reduction techniques tackle arbitrary
systems of linear Diophantine equations. Such techniques
generalize easily to similar coefficient rings possessing a
Euclidean algorithm, e.g. polynomial rings F[x] over a field, 
Gaussian integers Z[i]. There are many analogous interesting
methods, e.g. search on keywords: Hermite / Smith normal form, 
invariant factors, lattice basis reduction, continued fractions,
Farey fractions / mediants, Stern-Brocot tree / diatomic sequence.   

Nota: $ $ Como optimización, podemos omitir una de las columnas del coeficiente de Bezout (siendo derivable de las otras). Entonces los cálculos tienen un interpretación natural como fracciones modulares (aunque las "fracciones" son multivalores ), por ejemplo, calculando $\,\color{#c00}{\large \frac{-10}9}\equiv\color{#90f}{18}\pmod{\!43}\,$ como en esta respuesta

$$ \begin{array}{rr} \bmod 43\!:\ \ \ \ \ \ \ \ [\![1]\!] &43\, x\,\equiv\ \ 0\ \\ [\![2]\!] &\ \color{#c00}{9\,x\, \equiv -10}\!\!\!\\ [\![1]\!]-5\,[\![2]\!] \rightarrow [\![3]\!] & \color{#0a0}{-2\,x\, \equiv\ \ 7}\ \\ [\![2]\!]+\color{orange}4\,[\![3]\!] \rightarrow [\![4]\!] & \color{#90f}{1\,x\, \equiv 18}\ \end{array}\qquad\qquad\qquad$$

$$\dfrac{0}{43}\ \overset{\large\frown}\equiv \underbrace{\color{#c00}{\dfrac{-10}{9}}\ \overset{\large\frown}\equiv \ \color{#0a0}{\dfrac{7}{-2}}\ \overset{\large\frown}\equiv\ \color{#90f}{\dfrac{18}{1}}} _{\!\!\!\Large \begin{align}\color{#c00}{-10}\ \ + \ \ &\!\color{orange}4\,(\color{#0a0}{\ \, 7\ \, }) \ \ \equiv \ \ \color{#90f}{18}\\ \color{#c00}{9}\ \ +\ \ &\!\color{orange}4\,(\color{#0a0}{-2} ) \ \ \equiv\ \ \ \color{#90f}{1}\end{align}}\quad $$

También utilizamos residuos de menor magnitud $\,(\color{#0a0}{-2}\,$ contra. $7\bmod 9)\,$ para acortar los cálculos (esto puede reducir a la mitad el número de pasos en el algoritmo euclidiano).

Introducción a las operaciones de fila (para los lectores que no estén familiarizados con el álgebra lineal).

Dejemos que $\,r_i\,$ sea la sucesión de restos euclidianos. Por encima de $\, r_1,r_2,r_3\ldots = 80,62,18\ldots$ Dadas las combinaciones lineales $\,r_j = a_j m + b_j n\,$ para $\,r_{i-1}\,$ y $\,r_i\,$ podemos calcular una combinación lineal para $\,r_{i+1} := r_{i-1}\bmod r_i = r_{i-1} - q_i r_i\,$ sustituyendo dichas combinaciones por $\,r_{i-1}\,$ y $\,r_i,\,$ es decir

$$\begin{align} r_{i+1}\, &=\, \overbrace{a_{i-1} m + a_{i-1}n}^{\Large r_{i-1}}\, -\, q_i \overbrace{(a_i m + b_i n)}^{\Large r_i}\\[.3em] {\rm i.e.}\quad \underbrace{r_{i-1} - q_i r_i}_{\Large r_{i+1}}\, &=\, (\underbrace{a_{i-1}-q_i a_i}_{\Large a_{i+1}})\, m\, +\, (\underbrace{b_{i-1} - q_i b_i}_{\Large b_{i+1}})\, n \end{align}$$

Así, el $\,a_i,b_i\,$ satisfacen la misma recurrencia que los restos $\,r_i,\,$ a saber $\,f_{i+1} = f_{i-1}-q_i f_i.\,$ Esto implica que podemos realizar la recurrencia en paralelo sobre los vectores fila $\,[r_i,a_i,b_i]$ representando la ecuación $\, r_i = a_i m + b_i n\,$ como sigue

$$\begin{align} [r_{i+1},a_{i+1},b_{i+1}]\, &=\, [r_{i-1},a_{i-1},b_{i-1}] - q_i [r_i,a_i,b_i]\\ &=\, [r_{i-1},a_{i-1},b_{i-1}] - [q_i r_i,q_i a_i, q_i b_i]\\ &=\, [r_{i-1}-q_i r_i,\ a_{i-1}-q_i a_i,\ b_{i-1}-q_i b_i] \end{align}$$

que escrito en el formato tabular empleado más arriba se convierte en

$$\begin{array}{ccc} &r_{i-1}& a_{i-1} & b_{i-1}\\ &r_i& a_i &b_i\\ \rightarrow\ & \underbrace{r_{i-1}\!-q_i r_i}_{\Large r_{i+1}} &\underbrace{a_{i-1}\!-q_i a_i}_{\Large a_{i+1}}& \underbrace{b_{i-1}-q_i b_i}_{\Large b_{i+1}} \end{array}$$

Así, el ampliado El paso euclidiano es: calcular el cociente $\,q_i = \lfloor r_{i-1}/r_i\rfloor$ entonces multiplica la fila $i$ por $q_i$ y restarlo de la fila $i\!-\!1.$ Dicho por componentes: en cada columna $\,r,a,b,\,$ multiplicar el $i$ 'th entry by $q_i$ y luego restarlo del $i\!-\!1$ y se obtiene el $i\!+\!1$ de la entrada. Si ignoramos las columnas 2 y 3 $\,a_i,b_i$ entonces este es el algoritmo euclidiano habitual. Lo anterior extiende este algoritmo para calcular simultáneamente la representación de cada resto como una combinación lineal de $\,m,n,\,$ partiendo de las representaciones iniciales obvias $\,m = 1(m)+0(n),\,$ y $\,n = 0(m)+1(n).\,$

Answer 2

Esto es más un comentario sobre el método explicado por Bill Dubuque que una respuesta propiamente dicha, pero creo que hay una observación tan obvia que no entiendo que casi nunca se haga en los textos que hablan del algoritmo euclidiano extendido. Se trata de la observación de que se puede ahorrar la mitad del trabajo calculando sólo un de los coeficientes de Bezout. En otras palabras, en lugar de registrar por cada nuevo resto $r_i$ un par de coeficientes $k_i,l_i$ para que $r_i=k_ia+l_ib$ , sólo tiene que grabar $k_i$ tal que $r_i\equiv k_ia\pmod b$ . Una vez que haya encontrado $d=\gcd(a,b)$ y $k$ tal que $d\equiv ka\pmod b$ , puede entonces poner simplemente $l=(d-ka)/b$ para obtener el otro coeficiente de Bezout. Esta simplificación es posible porque la relación que da el siguiente par de coeficientes intermedios es perfectamente independiente para los dos coeficientes: digamos que se tiene $$ \begin{aligned} r_i&=k_ia+l_ib\\ r_{i+1}&=k_{i+1}a+l_{i+1}b\end{aligned} $$ y la división euclidiana da $r_i=qr_{i+1}+r_{i+2}$ entonces para obtener $$ r_{i+2}=k_{i+2}a+l_{i+2}b $$ se puede tomar $k_{i+2}=k_i-qk_{i+1}$ y $l_{i+2}=l_i-ql_{i+1}$ donde la ecuación para $k_{i+2}$ no necesita $l_i$ o $l_{i+1}$ para que puedas olvidarte de la $l$ 's. En forma de matriz, el pasaje es de $$ \begin{pmatrix} r_i&k_i&l_i\\ r_{i+1}&k_{i+1}&l_{i+1}\end{pmatrix} \quad\text{to}\quad \begin{pmatrix} r_{i+2}&k_{i+2}&l_{i+2}\\ r_{i+1}&k_{i+1}&l_{i+1}\end{pmatrix} $$ restando la segunda fila $q$ veces de la primera, y está claro que las dos últimas columnas son independientes, y uno podría quedarse con la $r$ y el $k$ 's, pasando de $$ \begin{pmatrix} r_i&k_i\\ r_{i+1}&k_{i+1}\end{pmatrix} \quad\text{to}\quad \begin{pmatrix} r_{i+2}&k_{i+2}\\ r_{i+1}&k_{i+1}\end{pmatrix} $$ en su lugar.

Un inconveniente menor es que la relación $r_i=k_ia+l_ib$ que debería mantenerse para cada fila es quizás un poco más fácil de comprobar por inspección que $r_i\equiv k_ia\pmod b$ para que los errores de cálculo puedan colarse con más facilidad. Pero realmente, creo que con algo de práctica este método es igual de seguro y más rápido que calcular ambos coeficientes. Ciertamente, al programar esto en un ordenador no hay ninguna razón para llevar la cuenta de ambos coeficientes.

Una última ventaja es que en muchos casos en los que se aplica el algoritmo euclidiano ampliado sólo interesa uno de los coeficientes de Bezout en primer lugar, lo que ahorra el paso final de calcular el otro. Un ejemplo es el cálculo de la inversa del módulo de un número primo $p$ Si se toma $b=p$ y $a$ no es divisible por él, entonces sabes de antemano que encontrarás $d=1$ y el coeficiente $k$ tal que $d\equiv ka\pmod p$ es simplemente la inversa de $a$ modulo $p$ que buscabas.

Answer 3

Tal vez quiera comprobar este y este .

Además, existe un conocido método de la tabla que es muy fácil y rápido para la solución manual.

Answer 4

La forma de hacerlo se debe a Blankinship "A New Version of the Euclidean Algorithm", AMM 70:7 (Sep 1963), 742-745. Digamos que queremos $a x + b y = \gcd(a, b)$ para simplificar con el positivo $a$ , $b$ con $a > b$ . Configurar los vectores auxiliares $(x_1, x_2, x_3)$ , $(y_1, y_2, y_3)$ y $(t_1, t_2, t_3)$ y mantenerlos de manera que siempre tengamos $x_1 a + x_2 b = x_3$ , $y_1 a + y_2 b = y_3$ , $t_1 a + t_2 b = t_3$ en todo. El algoritmo en sí es:

(x1, x2, x3) := (1, 0, a)
(y1, y2, y3) := (0, 1, b)
while y3 <> 0 do
    q := floor(x3 / y3)
    (t1, t2, t3) := (x1, x2, x3) - q * (y1, y2, y3)
    (x1, x2, x3) := (y1, y2, y3)
    (y1, y2, y3) := (t1, t2, t3)

Al final, $x_1 a + x_2 b = x3 = \gcd(a, b)$ . Se ve que $x_3$ , $y_3$ hacer como el algoritmo euclidiano clásico, y comprobar fácilmente que el invariante mencionado se mantiene todo el tiempo.

Se puede prescindir de $x_2$ , $y_2$ , $t_2$ y recuperar $x_2$ al final como $(x_3 - x_1 a) / b$ .

Answer 5

Para complementar las otras respuestas, hay una forma alternativa del algoritmo euclidiano extendido que no requiere retroceso, y que puede resultar más fácil de entender y aplicar. A continuación te explicamos cómo resolver tu problema* utilizándolo: $\newcommand{\x}{\phantom} \newcommand{\r}{\color{red}} \newcommand{\g}{\color{green}} \newcommand{\b}{\color{blue}}$

*) de una pregunta duplicada para el que escribí originalmente esta respuesta.

$$\begin{aligned} \g{ 0} \cdot 19 + \r{\x+1} \cdot 29 &= \b{ 29} && (1) \\ \g{ 1} \cdot 19 + \r{\x+0} \cdot 29 &= \b{ 19} && (2) \\ \g{-1} \cdot 19 + \r{\x+1} \cdot 29 &= \b{ 10} && (3) = (1) - (2) \\ \g{ 2} \cdot 19 + \r{ -1} \cdot 29 &= \b{\x09} && (4) = (2) - (3) \\ \g{-3} \cdot 19 + \r{\x+2} \cdot 29 &= \b{\x01} && (5) = (3) - (4) \end{aligned}$$

y ahora tienes tu solución: $\g{-3} \cdot 19 \equiv \b{1} \pmod{29}$ por lo que la inversa de $19$ modulo $29$ es $-3$ (o $29 - 3 = 27$ si se prefiere una solución no negativa).

En efecto, lo que estamos haciendo es tratar de encontrar una solución a la ecuación lineal $\g x \cdot 19 + \r k \cdot 29 = \b r$ con la menor cantidad posible de $\b r > 0$ . Para ello, comenzamos con las dos soluciones triviales $(1)$ y $(2)$ arriba, y luego generar nuevas soluciones con un $\b r$ restando siempre ambos lados de la última solución de la anterior tantas veces como sea necesario para obtener un $\b r$ de lo que tenemos hasta ahora . (En tu ejemplo, eso es sólo una vez cada vez, pero mostraré otro ejemplo más adelante en el que ese no es el caso).

Al final, encontraremos una solución con $\b r = 1$ en cuyo caso el correspondiente $\g x$ El coeficiente es el inverso que queremos, o terminaremos con $\b r = 0$ , en cuyo caso el anterior de la solución $\b r > 1$ es el máximo común divisor del número que intentamos invertir y el módulo, por lo que no existe ninguna inversa. (Por supuesto, también podríamos seguir hasta $\b r = 0$ en cualquier caso, y luego comprobar la línea anterior para ver si $\b r$ allí es igual a $1$ o no, pero eso sería un trabajo extra que podemos evitar fácilmente).

Además, cabe destacar que en realidad no estamos utilizando el $\r k$ coeficientes para cualquier cosa, así que si todo lo que te interesa es encontrar la inversa modular (y/o el GCD), no tienes que calcularlos. Pero mostrarlos lo hace más claro por qué el algoritmo funciona. (Además, si calcula $\r k$ es fácil verificar que no se ha cometido ningún error simplemente comprobando que la última ecuación con $\b r = 1$ realmente se mantiene).

---

De todos modos, aquí hay un par de ejemplos más trabajados para ilustrar algunos casos que tu ejemplo no tiene. Para empezar, vamos a intentar encontrar la inversa de $13$ modulo $29$ :

$$\begin{aligned} \g{ 0} \cdot 13 + \r{\x+1} \cdot 29 &= \b{ 29} && (1) \\ \g{ 1} \cdot 13 + \r{\x+0} \cdot 29 &= \b{ 13} && (2) \\ \g{-2} \cdot 13 + \r{\x+1} \cdot 29 &= \b{\x03} && (3) = (1) - 2 \cdot (2) \\ \g{ 9} \cdot 13 + \r{ -4} \cdot 29 &= \b{\x01} && (4) = (2) - 4 \cdot (3) \\ \end{aligned}$$

Esta vez, podíamos (y necesitábamos) restar la solución $(2)$ de $(1)$ dos veces, ya que $\lfloor 29 \mathbin/ 13 \rfloor = 2$ . Y, del mismo modo, podríamos restar $(3)$ de $(2)$ cuatro veces, ya que $\lfloor 13 \mathbin/ 3 \rfloor = 4$ . Y podemos comprobar que $\g 9$ es efectivamente la inversa de $13$ modulo $29$ simplemente comprobando que $9 \cdot 13 - 4 \cdot 29$ efectivamente es igual a $1$ .

Ahora probemos un ejemplo en el que la inversa sí lo hace no existen, como tratar de encontrar la inversa de $15$ modulo $27$ :

$$\begin{aligned} \g{ 0} \cdot 15 + \r{\x+1} \cdot 27 &= \b{ 27} && (1) \\ \g{ 1} \cdot 15 + \r{\x+0} \cdot 27 &= \b{ 15} && (2) \\ \g{-1} \cdot 15 + \r{\x+1} \cdot 27 &= \b{ 12} && (3) = (1) - (2) \\ \g{ 2} \cdot 15 + \r{ -1} \cdot 27 &= \b{\x03} && (4) = (2) - (3) \\ \g{-9} \cdot 15 + \r{\x+5} \cdot 27 &= \b{\x00} && (5) = (3) - 4 \cdot (4) \\ \end{aligned}$$

Oops. La última solución, con $\b r = 0$ es bastante inútil para nosotros (excepto para comprobar que hemos hecho bien la aritmética). A partir de la solución anterior $(4)$ Sin embargo, podemos leer que $\gcd(15, 27) = 3$ e incluso que $\g x = 2$ es una solución a la ecuación "inversa generalizada" $\g x \cdot 15 \equiv \gcd(15, 27) \pmod{27}$ .

---

Ps. Ver también esta respuesta que escribí en crypto.SE el año pasado explicando el mismo algoritmo desde un punto de vista ligeramente diferente.