El algoritmo de Euclides

Contenido

El algoritmo de Euclides#

Introducción#

Existen varios procedimientos para calcular el máximo común divisor. Un algoritmo eficiente es el Algoritmo de Euclides, nombrado por Euclides. En esta sección vamos a introducir el algoritmo de Euclides, el cual nos servirá para calcular el máximo común divisor de dos enteros positivos. Además de esto veremos que el algoritmo también nos brinda una forma mas sencilla y metódica de expresar el máximo común divisor de dos números como una combinación lineal.

Algoritmo de Euclides#

Veamos un teorema previo, el cual sentará las bases para el algoritmo de Euclides.

Proposición 12

Sean $a$ y $b$ enteros positivos y $r$ el residuo cuando $a$ es dividido por $b$. Entonces $(a,b)=(b,r).$

Demostración. Vamos a demostrar que $(a,b)=(b,r).$
Supongamos que $d=(a,b)$ y $d'=(b,r).$ Entonces debemos probar que $d=d'.$ Para ello tenemos que demostrar que $d|d'$ y $d'|d.$

Por el Teorema 3, tenemos que existen $q$ y $r$ enteros únicos tal que $a=bq+r.$

Primero probemos que $d|d'.$

Ahora probemos que $d'|d.$

Concluimos que como $d|d'$ y $d'|d$ por el inciso $6$ de la Proposición 2 $d'= d.$ Por lo tanto $(b,r)=(a,b). \square$

Ejemplo 38

Para ilustrar el teorema anterior, tomemos $a = 210$ y $b = 24.$

Veamos que los divisores de $24$ son $ \{1,2,3,4,6,8,12,24 \} $ y los divisores de $210$ son $\{ 1,2,3,5,6,7,10,14,15,21,30,35,42,70,105,210\}.$ Si interceptamos estos conjuntos tenemos el conjunto $\{ 1,2,3,6 \},$ por lo tanto $6$ es el mayor elemento del conjunto y así $(210,24) = 6.$

Ahora si aplicamos el Teorema 3 tendríamos que $210 = 8 \cdot 24 + 18.$
Entonces los divisores de $24$ son $\{ 1,2,3,4,6,8,12,24 \}$ y los divisores de $18$ son $\{ 1,2,3,6,9,18 \}.$ Si interceptamos estos conjuntos tenemos el conjunto $\{ 1,2,3,6 \},$ por lo tanto como $6$ es el mayor elemento del conjunto entonces $(24,18) = 6.$
Por lo tanto se cumple que $(210,24) = (24,18) = 6.$

Ahora si aplicamos nuevamente el Teorema 3 tendríamos que $24 = 1 \cdot 18 + 6.$
Entonces los divisores de $18$ son $\{ 1,2,3,6,9,18 \}$ y los divisores de $6$ son $\{ 1,2,3,6 \}.$ La intersección de estos dos conjuntos sería $\{ 1,2,3,6 \},$ por lo tanto $(18,6) = 6.$
Y ahora tendríamos que $(210,24) = (24,18) = (18,6) = 6.$

Teorema 13 (Algoritmo de Euclides)

Sean $a$ y $b$ cuales quiera dos enteros positivos con $a \ge b$. Si $a = b,$ entonces $(a,b) = a,$ por tanto asumiremos que $a > b > 0.$ (Si no se cumple simplemente los intercambiamos $a$ con $b$.) Sea $r_0 = a$ y $r_1 = b.$ Si el Teorema 3 es aplicado sucesivamente para obtener $r_j = r_{j+1}q_{j+1} + r_{j+2},$ con $0 < r_{j+2} < r_{j+1}$ para $j = 0,1,2,\ldots ,n-2$ y $r_{n+1} = 0,$ entonces $(a,b) = r_n,$ el último residuo que no es cero.

Demostración. Sean $r_0 = a$ y $r_1 = b$ enteros positivos tales que $a \ge b.$ Aplicando sucesivamente el Teorema 3, podemos obtener la siguiente sucesión de ecuaciones

\[\begin{align*} r_0 &= r_1q_1 + r_2 &0\le r_2 < r_1, \\ r_1 &= r_2q_2 + r_3 &0\le r_3 < r_2, \\ r_2 &= r_3q_3 + r_4 &0\le r_4 < r_3, \\ &\vdots \\ r_{j-2} &= r_{j-1}q_{j-1} + r_j &0\le r_j < r_{j-1}, \\ &\vdots \\ r_{n-4} &= r_{n-3}q_{n-3} + r_{n-2} &0\le r_{n-2} < r_{n-3}, \\ r_{n-3} &= r_{n-2}q_{n-2} + r_{n-1} &0\le r_{n-1} < r_{n-2}, \\ r_{n-2} &= r_{n-1}q_{n-1} + r_n &0\le r_n < r_{n-1}, \\ r_{n-1} &= r_nq_n. \end{align*}\]

Eventualmente obtendremos un residuo de cero ya que la secuencia de los residuos va descendiendo, es decir, $a = r_o \ge r_1 > r_2 > \ldots \ge 0,$ además no puede contener mas de $a$ términos.
Luego por la Proposición 12 podemos ver que

\[(a,b) = (r_0,r_1) = (r_2,r_3) = \ldots = (r_{n-3},r_{n-2}) = (r_{n-2},r_{n-1}) = (r_{n-1},r_n) = (r_n,0) = r_n.\]

Por lo tanto $(a,b) = r_n,$ el cual es el último residuo que no es cero.$\square$

Ejemplo 39

Aplica el algoritmo de Euclides para encontrar $(4076,1024).$

Solución.
Si aplicamos sucesivamente el algoritmo de la división tomando $a=4076$ y $b=1024$ obtenemos:

\[\begin{align*} 4076 &= 3\cdot 1024 + 1004 \\ 1024 &= 1\cdot 1004 + 20 \\ 1004 &= 50\cdot 20 + 4 \\ 20 &= 5\cdot 4 + 0. \end{align*}\]

Por lo tanto el último residuo que no es cero es $4$ y así $(4076,1024) = 4.$ Además

\[(4076,1024) = (1024,1004) = (1024,20) = (20,4) = 4.\]

Código para el algoritmo de Euclides#

El siguiente código calcula el el máximo común divisor de dos enteros utilizando el algoritmo de Euclides. Además nos mostrará todas las ecuaciones obtenidas tras aplicar el algoritmo de la división repetidas veces. El algoritmo nos pide que introduzcamos $a > b$ y en caso de ser $a < b$ intercambiarlos. En el caso en el que introduzcamos que $a < b,$ el código lo que hace es iniciar con la ecuación $a = bq + r$ tomando $q = 0$ y $r = a$ esto hace que los valores se inviertan y en la siguiente ecuación continue con los números en el orden $a > b.$

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        print(a,"=",b,"x",a//b,"+",a%b)
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return print("El máximo común divisor es: ",b)

algoritmo_euclides(4076,1024)

= 1024 x 3 + 1004
= 1004 x 1 + 20
= 20 x 50 + 4
El máximo común divisor es:  4

algoritmo_euclides(65432,4567)

= 4567 x 14 + 1494
= 1494 x 3 + 85
= 85 x 17 + 49
= 49 x 1 + 36
= 36 x 1 + 13
= 13 x 2 + 10
= 10 x 1 + 3
= 3 x 3 + 1
El máximo común divisor es:  1

algoritmo_euclides(2348,3588)

= 3588 x 0 + 2348
= 2348 x 1 + 1240
= 1240 x 1 + 1108
= 1108 x 1 + 132
= 132 x 8 + 52
= 52 x 2 + 28
= 28 x 1 + 24
= 24 x 1 + 4
El máximo común divisor es:  4

algoritmo_euclides(3588,2348)

= 2348 x 1 + 1240
= 1240 x 1 + 1108
= 1108 x 1 + 132
= 132 x 8 + 52
= 52 x 2 + 28
= 28 x 1 + 24
= 24 x 1 + 4
El máximo común divisor es:  4

El máximo común divisor como combinación lineal.#

Como vimos en el Lema 3 y en el Ejemplo 33 es posible reescribir el máximo común divisor de dos números como una combinación lineal de números enteros, es decir, una suma de la forma $\alpha a + \beta b,$ en donde $\alpha$ y $\beta$ son enteros. A continuación vamos a ver un ejemplo de como podemos utilizar el algoritmo de Euclides para encontrar dicha combinación lineal.

Ejemplo 40

Expresa (574,252) como una combinación lineal entera.
Solución.
Primero usemos el Teorema 13 para encontrar el máximo común divisor.

\[\begin{align*} 574 &= 252\cdot 2 + 70, \\ 252 &= 70\cdot 3 + 42, \\ 70 &= 42\cdot 1 + 28, \\ 42 &= 28\cdot 1 + 14, \\ 28 &= 14\cdot 2 + 0. \\ \end{align*}\]

Por lo tanto $(574,252)=14.$

Ahora utilizaremos las ecuaciones anteriores para ir sustituyendo de manera inversa.

\[\begin{split}\begin{cases} 14 = 42 - 28\cdot 1 \ldots (1) \\ 28 = 70 - 42\cdot 1 \ldots (2) \\42 = 252 - 70\cdot 3 \ldots (3) \\ 70 = 574 - 252\cdot 2 \ldots (4) \end{cases}\end{split}\]

Entonces tendríamos lo siguiente:

\[\begin{align*} 14 &= 42 - 28\cdot 1 \\ &= 42 - (70 - 42\cdot 1) \cdot 1 \quad \text{ (sustituyendo la ecuación $2$)} \\ &= 42\cdot 1 - 70\cdot 1 + 42\cdot 1 \\ &= 42\cdot 2 - 70\cdot 1 \\ &= (252 - 70\cdot 3)\cdot 2 - 70\cdot 1 \quad \text{ (sustituyendo la ecuación $3$)} \\ &= 252\cdot 2 - 70\cdot 6 - 70\cdot 1 \\ &= 252\cdot 2 - 70\cdot 7 \\ &= 252\cdot 2 - (574 - 252\cdot 2)\cdot 7 \quad \text{ (sustituyendo la ecuación $4$)} \\ &= 252\cdot 2 - 574\cdot 7 + 252\cdot 14 \\ &= 252\cdot 16 - 574\cdot 7 \end{align*}\]

Por lo tanto la combinación lineal es: $14=252\cdot 16-574\cdot 7.$

Algoritmo extendido de Euclides#

El método mostrado en el Ejemplo 40 para expresar el máximo común divisor $(a,b)$ como una combinación lineal de $a$ y $b$ es algo extenso debido a los cálculos realizados, es necesario aplicar el algoritmo de Euclides, guardar las ecuaciones generadas y hacer la sustitución de los valores de manera inversa en las ecuaciones para poder obtener la combinación lineal.
Existe otro método para obtener la combinación lineal que estamos buscando. Este requiere seguir los pasos del algoritmo de Euclides solo una vez. El siguiente teorema proporciona este método, que se denomina algoritmo extendido de Euclides.

Teorema 14 (Algoritmo extendido de Euclides)

Sean $a$ y $b$ enteros positivos. Entonces

\[(a,b) = s_na + t_nb,\]

en donde $s_n$ y $t_n$ son los n-ésimos términos de la secuencia definida recursivamente por:

\[\begin{align*} s_0 &= 1, &\quad t_0 &= 0, \\ s_1 &= 0, &\quad t_1 &= 1, \\ \text{y} \\ s_j &= s_{j-2} - q_{j-1}s_{j-1}, &\quad t_j &= t_{j-2} - q_{j-1}t_{j-1}, \end{align*}\]

para $j = 2,3,\ldots,n,$ en donde $q_j$ son los coeficientes de las divisiones en el algoritmo de Euclides cuando es usado para encontrar el $(a,b).$

Demostración. Procederemos por inducción.
Sea $P(j)$ la proposición que afirma que para el entero positivo $j$ se cumple que

\[r_j = s_ja + t_jb.\]

Base inductiva. Verifiquemos que $P(0)$ y $P(1)$ son verdaderas.

Para $j=0$ tenemos que: $a = r_0 = 1\cdot a + 0\cdot b = s_0a + t_0b.$
Para $j=1$ tenemos que: $b = r_1 = 0\cdot a + 1\cdot b = s_1a + t_1b.$

Hipótesis inductiva. Supongamos que $P(j)$ es verdadera para algún entero positivo $j,$ es decir que para $j = 1,2,\ldots,k-1$ se cumple que
\[r_j = s_ja + t_jb.\]
Paso inductivo. Nos gustaría probar que $P(k-1)$ implica $P(k).$

Entonces, del k-ésimo paso del algoritmo de Euclides, tenemos que

\[r_k = r_{k-2} - r_{k-1}q_{k-1}.\]

Usando la hipótesis de inducción, encontramos que:

\[\begin{align*} r_k &= (s_{k-2}a + t_{k-2}b) - (s_{k-1}a + t_{k-1}b)q_{k-1} \\ &= s_{k-2}a + t_{k-2}b - s_{k-1}aq_{k-1} - t_{k-1}bq_{k-1} \\ &= s_{k-2}a - s_{k-1}aq_{k-1} + t_{k-2}b - t_{k-1}bq_{k-1} \\ &= (s_{k-2} - s_{k-1}q_{k-1})a + (t_{k-2} - t_{k-1}q_{k-1}) \\ &= s_ka + t_kb. \end{align*}\]

Ya que $(a,b) = r_n,$ tenemos que $(a,b) = s_na + t_nb. \square$

Ejemplo 41

Usa el Teorema 14 para encontrar la combinación lineal de $(574,252) = 14.$

Solución.
Tenemos que $r_0 = 574$ y $r_1 = 252.$

Para $j = 0$ tenemos:

\[\begin{align*} r_0 &= r_1q_1 + r_2 & &\quad s_0 = 1 \\ 574 &= 252\cdot 2 + 70 & &\quad t_0 = 0 \\ \end{align*}\]

Para $j = 1$ tenemos:

\[\begin{align*} r_1 &= r_2q_2 + r_3 & &\quad s_1 = 0 \\ 252 &= 70\cdot 3 + 42 & &\quad t_1 = 1 \\ \end{align*}\]

Para $j = 2$ tenemos:

\[\begin{align*} r_2 &= r_3q_3 + r_4 & &\quad s_2 = s_0 - s_1q_1 = 1-0\cdot 2 = 1 \\ 70 &= 42\cdot 1 + 28 & &\quad t_2 = t_0 - t_1q_1 = 0 - 1\cdot 2 = -2 \\ \end{align*}\]

Para $j = 3$ tenemos:

\[\begin{align*} r_3 &= r_4q_4 + r_5 & &\quad s_3 = s_1 - s_2q_2 = 0-1\cdot 3 = -3 \\ 42 &= 28\cdot 1 + 14 & &\quad t_3 = t_1 - t_2q_2 = 1 - (-2)\cdot 3 = 7 \\ \end{align*}\]

Para $j = 4$ tenemos:

\[\begin{align*} r_4 &= r_5q_5 + r_6 & &\quad s_4 = s_2 - s_3q_3 = 1-(-3)\cdot 1 = 4 \\ 28 &= 14\cdot 2 + 0 & &\quad t_4 = t_2 - t_3q_3 = -2 - 7\cdot 1 = -9 \\ \end{align*}\]

Para $j = 5$ solo hace falta calcular $s_5$ y $t_5:$

\[\begin{align*} s_5 &= s_3-s_4q_4 &\quad t_5 &= t_3 - t_4q_4 \\ &= -3 - 4\cdot 1 = -7 &\quad &= 7 - (-9)\cdot 1 = 16 \end{align*}\]

Por lo tanto tenemos que:

\[\begin{align*} r_5 &= s_5a + t_5b \\ 14 &= -7\cdot 574 + 16\cdot 252 \end{align*}\]

Código para encontrar la combinación lineal#

El siguiente código calcula como expresar el máximo común divisor de dos números $a$ y $b$ como una combinación lineal de los números $a$ y $b.$

def euclides_extendido_ciclos(a,b):
    num1 = a
    num2 = b
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return print(f"La combinación lineal de {num1} y {num2} es: {num1}({s[-2]}) + {num2}({t[-2]}) = {a}")

euclides_extendido_ciclos(574,252)

La combinación lineal de 574 y 252 es: 574(-7) + 252(16) = 14

euclides_extendido_ciclos(4076,1024)

La combinación lineal de 4076 y 1024 es: 4076(51) + 1024(-203) = 4

euclides_extendido_ciclos(65432,4567)

La combinación lineal de 65432 y 4567 es: 65432(-1397) + 4567(20015) = 1

Explicación del código#

En esta sección vimos la sentencia while. En Python se utiliza para ejecutar un bloque de código repetidamente mientras se cumpla una condición específica. La estructura básica de un bucle while es la siguiente:

while condición: 
    Bloque de código
    a repetir

Antes de ejecutar el bloque de código dentro del bucle while, Python evalúa la condición. La condición es una expresión que devuelve un valor booleano. Si la condición es True, el bloque de código dentro del while se ejecuta. Una vez que se completa la ejecución del bloque de código, la ejecución regresa al principio del while y se evalúa nuevamente la condición. Este proceso se repite hasta que la condición se vuelva False. Si la condición resulta ser False, el bloque de código no se ejecuta y el programa continúa con la siguiente línea de código después del while.

En esta ocasión usamos la sentencia != la cual comprueba si dos valores no son iguales. Es un operador de comparación que devuelve el valor True si los valores comparados son diferentes y False si son iguales.
El siguiente ejemplo devolvería un valor de True en la consola.

3 != 5

El siguiente ejemplo devolvería un valor de False

5 != 5

En Python podemos hacer una asignación múltiple, es decir:

a,b = x,y

Python entenderá que la variable $a = x$ y la variable $b = y.$ No hay un límite en las variables que podemos asignar de esta manera, solo hay que tener cuidado en tener la misma cantidad de variables en ambos lados de la igualdad.

Anteriormente vimos que podemos seleccionar elementos de una lista, sin embargo si deseamos recorrer los elementos de una lista en orden inverso, es decir, del último al primero, puedes utilizar índices negativos. Los índices negativos comienzan desde -1, que representa el último elemento de la lista, y van hacia atrás hasta -n, donde n es la longitud de la lista. Por ejemplo si quisiéramos seleccionar el penúltimo elemento de una lista con $5$ elementos lista tendríamos los siguiente:

lista = [1,2,3,4,5]
lista[-2]

La letra f al inicio de la función print en Python se utiliza para indicar que se está formateando una cadena de texto (string) utilizando f-strings, también conocidas como cadenas formateadas. Las f-strings son una característica de Python que permite incrustar expresiones dentro de cadenas de texto de una manera más legible y conveniente.
Cuando usamos una f-string, podemos incluir variables y expresiones directamente dentro de la cadena de texto, encerrándolas entre llaves {}. Python evaluará estas expresiones y las sustituirá por sus valores correspondientes cuando se imprima la cadena. Por ejemplo:

nombre = "Juan"
edad = 30
print(f"Mi nombre es {nombre} y tengo {edad} años.")

Cuando se imprime la cadena utilizando la función print, Python sustituirá {nombre} por el valor de la variable nombre (en este caso, «Juan») y {edad} por el valor de la variable edad (en este caso, 30). Obteniendo en la consola: «Mi nombre el Juan y tengo $30$ años.»

Veamos como funciona el primer código.

def algoritmo_euclides(a,b):
    while (a % b) != 0:
        print(a,"=",b,"x",a//b,"+",a%b)
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1
    return print("El máximo común divisor es: ",b)

Creamos una función llamada «algoritmo_euclides» la cual recibe como argumento dos enteros positivos.

def algoritmo_euclides(a,b):

Empezamos un ciclo while el cual va a repetir el bloque de código dentro de él siempre y cuando la condición a % b !=0 siga siendo verdadera. Esto es que el residuo de dividir $a$ entre $b$ siga siendo diferente de cero.

    while (a % b) != 0:

Mientras la condición del ciclo while siga siendo verdadera. El código primero va a imprimir en la consola la forma $a = bq + r,$ después va a intercambiar los valores, a la variable $a$ le asigna el valor de $b$ y a la variable $b$ le asigna el valor de $r.$

        print(a,"=",b,"x",a//b,"+",a%b)
        a_1, b_1 = a, b
        a = b_1
        b = a_1 % b_1

Una vez que el ciclo while se detenga el código nos mostrará el máximo común divisor de los números $a$ y $b.$

    return print("El máximo común divisor es: ",b)

Ahora veamos como funciona el segundo código.

def euclides_extendido_ciclos(a,b):
    num1 = a
    num2 = b
    s=[1,0]
    t=[0,1]
    while b!=0:
        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r
    return print(f"La combinación lineal de {num1} y {num2} es: {num1}({s[-2]}) + {num2}({t[-2]}) = {a}")

Creamos una función llamada «euclides_extendido_ciclos» la cual recibe como argumentos dos enteros positivos.

def euclides_extendido_ciclos(a,b):

Creamos dos variables $num1$ y $num2$ para guardar los valores originales de $a$ y $b,$ además creamos dos listas $s$ la cual tiene como elementos $1,0$ y $t$ la cual tiene como valores $0,1.$ Estos valores representan $s_0,s_1,t_0$ y $t_1$ respectivamente.

    num1 = a
    num2 = b
    s=[1,0]
    t=[0,1]

Empezamos un ciclo while el cual va a repetir el bloque de código dentro de él siempre y cuando la condición b != 0siga siendo verdadera. Esto es que mientras la variable $b$ sea diferente de cero, el bloque de código se seguirá ejecutando.

    while b!=0:

Empezamos obteniendo los valores para poder calcular los valores de $s_j = s_{j-2} + q_{j-1}s_{j-1}q$ y $t_j = t_{j-2} + q_{j-1}t_{j-1}.$ Obtenemos $q$ que es la parte entera de dividir $a$ entre $b$ y $r$ que es el residuo de dividir $a$ entre $b.$ Calculamos el valor de $s_j$ y $t_j$ guardando el valor en las variables «nuevo_s» y «nuevo_t», luego guardamos estos valores en las listas $s$ y $t.$ Al finalizar actualizamos los valores de $a$ y $b,$ a $a$ se le asignamos el valor de $b$ y a $b$ le asignamos el valor de $r.$

        q=a//b
        r=a%b
        nuevo_s=s[-2]-q*s[-1]
        nuevo_t=t[-2]-q*t[-1]
        s.append(nuevo_s)
        t.append(nuevo_t)
        a,b=b,r

Cuando el ciclo while se detiene el código nos imprime en la consola la combinación lineal.

    return print(f"La combinación lineal de {num1} y {num2} es: {num1}({s[-2]}) + {num2}({t[-2]}) = {a}")

Ejercicios de práctica#

Usa el algoritmo de Euclides para calcular el máximo común divisor y luego exprese como combinación lineal los siguientes números
- $1024,1000$
- $2076,1076$
- $3076,1876$
Usa el algoritmo de Euclides para ver que las expresiones $n^4 + 4n^3 + 8n^2 + 8n + 4$ y $n^3 + 3n^2 + 4n + 3$ son primos relativos para todo entero $n$.
Los números $75$ y $35$ tienen máximo común divisor igual a $5$. Por el algoritmo de Euclides, podemos entonces escribir a $5$ como combinación lineal de ellos. ¿Cuál es esta combinación lineal? Sabiendo esta combinación lineal,
- ¿Será posible poner a $105$ como combinación lineal de $75$ y $35$?
- ¿Será posible poner a $106$ como combinación lineal de $75$ y $35$? En las siguiente sección estudiaremos este problema con mayor generalidad.
Los números de Fibonacci son $F_0=0$, $F_1=1$ y para cada $n\geq 0$, cumplen $F_{n+2}=F_n+F_{n+1}$. Así, comienzan siendo $0,1,1,2,3,5,8,\ldots$ y cada número nuevo es la suma de los últimos dos. Usando el algoritmo de Euclides, demuestra que,
- El máximo común divisor del número de Fibonacci $F_n$ y el $F_{n+1}$ siempre es $1$.
- Expresa a $1$ como combinación lineal de los Fibonaccis $F_n$ y $F_{n+1}$ usando las ideas de arriba.
- Demuestra que si $m$ y $n$ son enteros positivos, entonces $(F_m,F_n) = F_{(m,n)}.$
Veamos otro código que también encuentra la combinación lineal.
```
def euclides_extendido(a, b):
   if b == 0:
      return (1, 0, a)
   else:
      x, y, gcd = euclides_extendido(b, a % b)
      return (y, x - (a // b) * y, gcd)
```
- Juega con este código para ver que en efecto da los coeficientes apropiados.
- En este código, la función se cita a sí misma. A esto se le conoce como que esta función es recursiva.
- Demuestra que en efecto este código también es correcto.