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 tambien nos brinda una forma mas sencilla y métodica 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.

Proposition 7

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

Proof. 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 Theorem 2, tenemos que existen $q$ y $r$ enteros únicos tal que $a=bq+r.$

Primero probemos que $d|d'.$

Ahora probemos que $d'|d.$

Concluímos que como $d|d'$ y $d'|d$ por el inciso $6$ de la Proposition 3 $d'= d.$ Por lo tanto $(b,r)=(a,b). \square$

Example 20

Para ilustar 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 intersectamos 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 Theorem 2 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 intersectamos 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 Theorem 2 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.$

Theorem 7 (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 Theorem 2 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.

Proof. Sean $r_0 = a$ y $r_1 = b$ enteros positivos tales que $a \ge b.$ Aplicando sucesivamente el Theorem 2, 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 Proposition 7 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$

Example 21

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 cálcula 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 intriduzcamos el caso donde $a < b$ el código lo que hace es inicar 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 ya tengamos el caso $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 Lemma 2 y en el Example 16 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.

Example 22

Expresa (574,252) como una combinación lineal entera.
Solución.
Primero usemos el Theorem 7 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\cdot - (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 Example 22 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.

Theorem 8 (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).$

Proof. 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 gustaria 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$

Example 23

Usa el Theorem 8 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 &= 251\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 \\ 574 &= 251\cdot 2 + 70 & &\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#

def euclides_extendido_ciclos(a,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 s[-2],t[-2],a

num1 = 574
num2 = 252
print(f"La combinación lineal de {num1} y {num2} es: {num1}({x}) + {num2}({y}) = {gcd}")

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

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)

# Ejemplo de uso
num1 = 574
num2 = 252
x, y, gcd = euclides_extendido(num1, num2)
print(f"La combinación lineal de {num1} y {num2} es: {num1}({x}) + {num2}({y}) = {gcd}")

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

euclides_extendido(574,252)

(-7, 16, 14)

euclides_extendido(252,574)

(16, -7, 14)

euclides_extendido(32,12)

(-1, 3, 4)

Ejercicios resueltos#

Corollary 4

Si $a$ y $b$ son primos relativos $(a,b)=1,$ y si $a|bc,$ entonces $a|c.$

Proof. Como $a$ y $b$ son primos relativos tenemos que $(a,b)=1.$ Entonces podemos reescribir el máximo común divisor como una combinación lineal con $\alpha$ y $\beta$ enteros, esto es, $\alpha a+\beta b=1.$ Luego si multiplicamos esta ecuación por $c$ tenemos que:

\[\alpha ac+\beta bc=c.\]

De lo anterior tenemos que $a | \alpha ac$ y $a | \beta bc,$ entonces $a| (\alpha ac+\beta bc)$ y por lo tanto $a|c. \square$

Explicación del 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)

Veamos como funciona el 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)

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^3+3n^2+n+1$ y $n^2+3n+1$ 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? Ya 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$. Después, expresa a $1$ como combinación lineal de los Fibonaccis $F_n$ y $F_{n+1}$ usando las ideas de arriba.
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.