El algoritmo de Euclides y el máximo común divisor

Introducción.

En este capítulo vamos a definir el concepto del máximo común divisor (MCD). Anteriormente, vimos que un número puede tener varios divisores. En esta ocasión veremos que dos números enteros cualesquiera siempre tienen al menos un divisor en común y al más grande de ellos es al que llamamos máximo común divisor. En nuestros cursos de secundaria llegamos a calcular el máximo común divisor de la siguiente manera. Si nos daban los números \(21\) y \(42\) y queríamos calcular su máximo común divisor, buscábamos sus respectivos divisores los cuales son \(\{1,3,7,21\}\) y \(\{1,2,3,6,7,21,42\}\) y resulta que el divisor más grande que tienen en común es el \(21\). Esta es una forma de calcularlo, pero mientras más grandes eran los números más complicados se hacían los cálculos.

Es aquí donde introducimos el algoritmo de Euclides. Dicho algoritmo nos brinda una manera más sencilla de calcular el máximo común divisor de dos enteros positivos. Además, este algoritmo nos será de mucha utilidad cuando entremos a resolver ecuaciones diofantinas y congruencias lineales, pero en este capítulo en específico será de ayuda para encontrar el máximo común divisor de dos números, así como una combinación lineal que lo genera.

Definición del máximo común divisor

Definición 11 (Máximo común divisor)

El máximo común divisor (mcd) de dos enteros \(a\) y \(b\), no ambos cero, es el entero positivo más grande que divide a \(a\) y \(b\) es denotado por \((a,b)\).

En otras palabras \(d = (a,b)\), si las siguientes dos condiciones se satisfacen:

1. \(d|a\) y \(d|b\).

2. Si \(d'|a\) y \(d'|b\), entonces \(d'|d\).

La segunda condición implica que de existir otro valor \(d'\) que dividida tanto a \(a\) como a \(b\), debe ser menor que el valor de \(d = (a,b)\).

Dado que \((a,-b)=(-a,b)=(-a,-b)=(a,b)\), limitaremos el estudio del máximo común divisor a enteros positivos.

Cuando dijimos que dos enteros siempre tienen un divisor en común es porque si tenemos dos números \(a\) y \(b\) es cierto que \(1|a\) y que \(1|b\). Entonces el máximo común divisor de dos números siempre existe.

Propiedades del máximo común divisor

Proposición 8

Sea \((a,b)=d\). Entonces se cumple lo siguiente:

1. \(\left( \frac{a}{d}, \frac{b}{d} \right)=1\).

2. \((a,a-b)=d\).

Demostración. 1
Sean \(\left( \frac{a}{d}, \frac{b}{d} \right)=d'\) y \((a,b) = d\).
Debemos demostrar que \(d'=1\). Ya que \(d'\) es un divisor común de \(\frac{a}{d}\) y \(\frac{b}{d}\) tenemos que existen \(l\) y \(m\) tales que,

\[\frac{a}{d} = ld' \quad \text{ y } \quad \frac{b}{d} = md'.\]

De las igualdades anteriores podemos despejar \(a\) y \(b\) obteniendo,

\[a =ldd' \quad \text{ y } \quad b = mdd'.\]

Podemos notar que \(dd'\) es un factor en común de \(a\) y \(b\). Por la Definición 11 y como \((a,b) = d\), tendríamos que \(dd'|d\), entonces \(dd'\le d\) y así \(d' \le 1\).

Luego, como \(d'\) es un entero positivo, concluimos que \(d'=1 \). Por lo tanto, si \((a,b)=d\), entonces \((\frac{a}{d}, \frac{b}{d}) = 1\). \(\square\)

Demostración. 2
Sean \((a,a-b)=d'\) y \((a,b) = d\).
Debemos demostrar que \(d = d'\), Para esto, vamos a demostrar que \(d|d'\) y luego que \(d'|d\).

• Primero probemos que \(d|d'\).

Ya que \((a,b) = d\) tendríamos que \(d|a\) y \(d|b\), luego por el inciso \(4\) de la Proposición 2 \(d|(a-b)\).
Así, podemos ver que \(d|a\) y \(d|(a-b)\). Por lo tanto, por definición \(d|d'\).

• Ahora, probemos que \(d'|d\).

Ya que \((a,a-b) = d'\), entonces \(d'|a\) y \(d'|(a-b)\), luego por el inciso \(5\) de la Proposición 2 \(d'|b\). Así, \(d'\) es un divisor en común de \(a\) y \(b\). Nuevamente por definición concluimos que \(d'|d\).

De ambos casos tenemos que \(d|d'\) y que \(d'|d\). Por el inciso \(6\) de la Proposición 2 y como ambos son positivos, podemos concluir que \(d = d'\). \(\square\)

Corolario 1

Sean \(a\), \(b\) y \(c\) enteros, entonces \((a+bc,b) = (a,b)\).

Demostración. Sean \(e = (a,b)\) y \(d = (a + bc, b)\). Vamos a demostrar que \(e = d\).

• Demostremos primero que \(e|d\).

Ya que \(e|a\) y \(e|b\), se tiene que \(e|bc\) y por el inciso \(4\) de la Proposición 2 tenemos que \(e|(a + bc)\). Entonces \(e|b\) y \(e|(a + bc)\) y por definición tenemos que \(e|d\).

• Ahora, demostremos que \(d|e\).

Ya que \(d|b\), sucede que \(d|bc\) y como \(d|(a+bc)\), por el inciso \(5\) de la Proposición 2 \(d|a\). Entonces \(d|a\) y \(d|b\) y por definición tenemos que \(d|e\).

De ambos casos obtenemos que \(e|d\) y \(d|e\). Por el inciso \(6\) de la Proposición 2 y como ambos son positivos, tenemos que \(e = d\) y así \((a+bc,b) = (a,b)\). \(\square\)

La definición del máximo común divisor da pie a las siguientes definiciones.

Definición 9 (Primos relativos)

Se dice que dos enteros \(a\) y \(b\) son primos relativos si su máximo común divisor es \(1\), es decir \((a,b)=1\).

Ejemplo 26

Por ejemplo \(6\) y \(35\) son primos relativos, ya que no comparten ningún divisor positivo mas que el \(1\). Por lo tanto \((6,35)=1\).

La definición de primos relativos se puede extender a un conjunto de números más grande en donde para cada par de números que tomemos de dicho conjunto son primos relativos. Veamos la definición formal de esto.

Definición 10 (Primos relativos por pares)

Los enteros positivos \(a_1,a_2,...,a_n\) son primos relativos por pares, si cada par de estos enteros son primos relativos, es decir, \((a_i,a_j)=1\) siempre que \(i \neq j\).

Ejemplo 27

Por ejemplo, los números \(8,15\) y \(49\) son primos relativos por pares, ya que \((8,15)=1, (15,49)=1\) y \((8,49)=1\).

La idea del máximo común divisor se puede extender a más de dos números.

Definición 11 (Máximo común divisor de \(n\) enteros)

El máximo común divisor (mcd) de los enteros \(a_1, a_2, \ldots ,a_n\), no todos cero, es el entero positivo más grande que divide a cada uno de los \(a_i\), donde \(i = 1,2,\ldots ,n\). Es denotado por \((a_1, a_2, \ldots ,a_n)\).

En otras palabras \(d = (a_1, a_2, \ldots ,a_n)\), si las siguientes condiciones se satisfacen:

1. \(d|a_i\), donde \(i = 1,2,\ldots, a_n\).

2. Si \(d'|a_i\), donde \(i = 1,2,\ldots ,a_n\), entonces \(d'|d\).

Veamos que para obtener el máximo común divisor de 3 o más enteros positivos podemos usar la recursión.

Teorema 7

Sea \(n\) un entero positivo y \(a_1,a_2,...,a_n\) enteros, donde \(n\ge 3\). Entonces

\[(a_1,a_2,...,a_n)=((a_1,a_2,...a_{n-1}),a_n).\]

Demostración. Sean \(d=(a_1,a_2,...,a_n)\), \(d'=(a_1,a_2,...,a_{n-1})\) y \(d''=(d',a_n)\). Probaremos que \(d = d''\).

• Primero probaremos que \(d|d''\).

Ya que \(d=(a_1,a_2,...,a_n)\), entonces \(d|a_i\) para toda \(1 \le i \le n\). En particular, como \(d|a_i\) para \(1 \le i \le n-1\) por definición tenemos que \(d|d'\), además \(d|a_n\) y por lo tanto \(d\mid d''\).

• Ahora, veamos que \(d''|d\).

Ya que \(d'' = (d',a_n)\), tenemos que \(d''|d'\) esto significa que \(d''|a_i\) para \(1\le i \le n-1\). Además, \(d''|a_n\) y así, \(d''|a_i\) para toda \(1\le i \le n\), con lo cual concluimos que \(d''| d\).

Luego, como \(d|d''\) y \(d''|d\) podemos concluir que \(d = d''\). \(\square\)

El lema de Bézout

En esta sección vamos a ver que el máximo común divisor de dos enteros \(a\) y \(b\) puede ser escrito como una suma o resta de múltiplos de \(a\) y \(b\). Para ello veamos la definición de una combinación lineal.

Definición 12 (Combinación lineal entera)

Si \(a\) y \(b\) son enteros, entonces una combinación lineal de \(a\) y \(b\) es una suma de la forma \(\alpha a + \beta b\), donde \(\alpha\) y \(\beta\) son enteros.

Ejemplo 28

Veamos algunas de las combinaciones lineales usando los enteros \(4\) y \(7\).

\[\begin{align*} 1\cdot 4 + (-1)\cdot 7 &= -3, \\ & \\ (-2)\cdot 4 + 1\cdot 7 &= -1, \\ & \\ 0\cdot 4 + 0\cdot 7 &= 0, \\ & \\ 2\cdot 4 + (-1)\cdot 7 &= 1, \\ & \\ (-1)\cdot 4 + 1\cdot 7 &= 3. \\ \end{align*}\]

En el ejemplo anterior podemos ver que \((4,7) = 1 = 2\cdot 4 + (-1)\cdot 7\). Vamos a ver con el siguiente lema que esta combinación es la más pequeña de las combinaciones lineales positivas.

Lema 2

El máximo común divisor de los enteros positivos \(a\) y \(b\) es la más pequeña de las combinaciones lineales positivas de \(a\) y \(b\).

Demostración. Sea \(S\) el conjunto de las combinaciones lineales de \(a\) y \(b\), esto es:

\[S = \{ ma+nb \mid ma+nb>0 , m , n \in \mathbb{Z} \}.\]

Veamos que \(S\) es no vacío.
Ya que \(a>0\), podemos reescribir \(a\) como \(a = 1\cdot a + 0\cdot b\), por lo cual \(1\cdot a + 0\cdot b \in S\), entonces \(S\) es no vacío. Luego por la Proposición 5, \(S\) tiene un único elemento mínimo digamos \(d\).

Ahora veamos que \(d = (a,b)\).

Como \(d \in S\), entonces \(d = \alpha a + \beta b\) para algunos enteros \(\alpha\) y \(\beta\).

• Primero veremos que \(d|a\) y \(d|b\).

Por el Teorema 3 sabemos que existen \(q\) y \(r\) tales que \(a = dq + r\), donde \(0 \le r <d\). Entonces tenemos lo siguiente,

\[\begin{align*} r &= a -dq \\ & \\ &= a - (\alpha a + \beta b)q \\ & \\ &= a - \alpha aq - \beta bq \\ & \\ & = (1 - \alpha q)a + (- \beta q)b. \end{align*}\]

Lo anterior muestra que \(r\) es una combinación lineal de \(a\) y \(b\).

Supongamos que \(r>0\), entonces \(r \in S\). Como \(r < d\), \(r\) sería un elemento más pequeño que \(d\) del conjunto \(S\), lo cual es una contradicción.
Entonces \(r = 0\) y asi \(a = dq\), por lo tanto \(d|a\). Análogamente, \(d|b\).

Por lo tanto, como \(d|a\) y \(d|b\), entonces \(d\) es un divisor común de \(a\) y \(b\).

• Por último veamos que cualquier otro divisor común \(d'\) de \(a\) y \(b\) es menor que \(d\).

Como \(d'|a\) y \(d'|b\), por la Proposición 2 tenemos que \(d'|(\alpha a + \beta b)\), por lo cual \(d'|d\).

Así, por lo anterior concluimos que \(d = (a,b)\). \(\square\)

Con el lema de Bézout podemos demostrar los siguientes resultados.

Teorema 8

Dos enteros positivos \(a\) y \(b\), son primos relativos si y sólo si existen enteros \(\alpha\) y \(\beta\) tal que \(\alpha a + \beta b = 1\).

Demostración. Tenemos que demostrar las dos implicaciones.

• Primero tomemos por hipótesis que \(a\) y \(b\) son primos relativos.

Entonces \((a,b) = 1\). Luego por el Lema 2 existen \(\alpha\) y \(\beta\) tales que \(\alpha a + \beta b = 1\).

• Ahora tomemos por hipótesis que \(\alpha a + \beta b = 1\).

Supongamos que \((a,b) = d\). Luego como \(d|a\) y \(d|b\) por la propiedad \(4\) de la Proposición 2 tenemos que \(d|(\alpha a + \beta b) = 1\), para algunos enteros \(\alpha\) y \(\beta\). De lo anterior concluimos que \(d|1\), entonces \(d = 1\). Por lo tanto, \((a,b)=1\). \(\square\)

,````{prf:corollary} :label: cor-mcd-propiedades2 Si \(a|c\) y \(b|c\) y además \((a,b)=1\), entonces \(ab|c\).

````{prf:proof}
Por hipótesis tenemos que $a|c$ y $b|c$, entonces existen $m$ y $n$ tales que, $$c = ma \quad \text{ y } \quad c = nb.$$

Además, como $(a,b) = 1$ por el {prf:ref}`lem-bezout` tenemos que $\alpha a + \beta b = 1$, para algunos enteros $\alpha$ y $\beta$.  
Ahora, si multiplicamos por $c$ la igualdad y luego sustituimos la primera $c$ por $nb$ y la segunda $c$ por $ma$, tendremos lo siguiente,
\begin{align*}
\alpha a + \beta b &= 1, \\
& \\
\alpha ac + \beta bc &= c, \\
& \\
\alpha anb + \beta bma &= c, \\
& \\
ab ( \alpha n + \beta m) &= c.
\end{align*}
Por lo tanto $ab|c$. $\square$ 

Corolario 2

Si \(a\) y \(b\) son primos relativos y \(a|bc\), entonces \(a|c\).

Demostración. Como \(a\) y \(b\) son primos relativos tenemos que \((a,b)=1\). Entonces, por el Teorema 8 podemos reescribir el máximo común divisor como una combinación lineal con \(\alpha\) y \(\beta\) cualesquiera 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\)

Algoritmo de Euclides

El algoritmo de Euclides es la herramienta con la cual vamos a calcular el máximo común divisor y además nos ayudará a encontrar la combinación lineal de dos enteros. Veamos un teorema previo, el cual sentará las bases para el algoritmo de Euclides.

Proposición 9

Sean \(a\) y \(b\) enteros positivos y \(r\) el residuo cuando \(a\) es dividido por \(b\), es decir \(a = bq + r\). 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\).

• Primero probemos que \(d|d'\).

Ya que \(d=(a,b)\), tenemos que \(d|a\) y \(d|b\). Entonces \(d|bq\) y por el inciso \(4\) de la Proposición 2 tenemos que \(d|(a-bq)\), esto quiere decir que \(d|r\). Así, tenemos que \(d|b\) y \(d|r\), entonces \(d|(b,r) = d'\).

• Ahora, probemos que \(d'|d\).

Similarmente, como \(d'=(b,r)\), tenemos que \(d'|r\) y \(d'|b\). Entonces \(d'|bq\) y se sigue que \(d'|(bq+r)\). Esto quiere decir que \(d'|a\). Como \(d'|a\) y \(d'|b\) entonces \(d'|(a,b) = d\).

De lo anterior tenemos que \(d|d'\) y \(d'|d\). Por el inciso \(6\) de la Proposición 2, \(d'= d\). Por lo tanto \((b,r)=(a,b)\). \(\square\)

El algoritmo de Euclides hace uso repetitivo del Teorema 3 hasta que obtengamos el máximo común divisor de dos enteros positivos.
Pensemos en los siguientes casos para calcular el máximo común divisor de dos enteros \(a\) y \(b\).

• Cuando \(a = b\), entonces \((a,b) = a\).

• Cuando \(a = 0\), entonces \((a,b) = b\).

Por lo tanto, en el algoritmo de Euclides asumiremos que \(a>b>0\).

Observación 2 (Algoritmo de Euclides)

Tomemos \(a\) y \(b\) cualesquiera dos enteros positivos, donde \(a > b\).

Aplicando repetidamente el Teorema 3, podemos obtener la siguiente sucesión de igualdades

\[\begin{align*} a &= bq_1 + r_1, \quad \text{donde}\quad 0\le r_1 < b; \\ & \\ b &= r_1q_2 + r_2, \quad \text{donde}\quad 0\le r_2 < r_1; \\ & \\ r_1 &= r_2q_3 + r_3 , \quad \text{donde}\quad 0\le r_3 < r_2; \\ & \vdots \\ r_{j-2} &= r_{j-1}q_{j} + r_j, \quad \text{donde}\quad 0\le r_j < r_{j-1}; \\ & \vdots \\ r_{n-3} &= r_{n-2}q_{n-1} + r_{n-1}, \quad \text{donde}\quad 0\le r_{n-1} < r_{n-2}; \\ & \\ r_{n-2} &= r_{n-1}q_{n} + r_n, \quad \text{donde}\quad 0\le r_n < r_{n-1}; \\ & \\ r_{n-1} &= r_nq_n + 0. \end{align*}\]

Eventualmente obtendremos un residuo cero ya que la secuencia de los residuos va descendiendo, es decir, \(r_1 > r_2 > r_3 > \ldots > r_{n-1}>r_n \), y como existe un número finito de enteros positivos menores que \(b\), el proceso debe terminar.

Luego, utilizando la Proposición 9 para cada una de las ecuaciones obtenidas, obtenemos que

\[(a,b) = (b,r_1) = (r_1,r_2) = \ldots = (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.

Ejemplo 29

Aplica el algoritmo de Euclides para encontrar el máximo común divisor de \(4076\) y \(1024\).

Solución.

Si aplicamos sucesivamente el algoritmo de la división para \(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) = (1004,20) = (20,4) = 4.\]

Código para calcular el MCD usando el algoritmo de Euclides

El siguiente código calcula el máximo común divisor de dos enteros utilizando el algoritmo de Euclides. Además, nos muestra todas las ecuaciones obtenidas tras aplicar el algoritmo de la división repetidas veces.
Una observación, 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)

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

algoritmo_euclides(65432,4567)

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

algoritmo_euclides(3588,2388)

3588 = 2388 x 1 + 1200
2388 = 1200 x 1 + 1188
1200 = 1188 x 1 + 12
El máximo común divisor es:  12

La combinación lineal usando el algoritmo de Euclides

Como vimos en el Lema 2, es posible expresar 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\), donde \(\alpha\) y \(\beta\) son enteros. A continuación vamos a ver un ejemplo de cómo podemos utilizar el algoritmo de Euclides para encontrar dicha combinación lineal.

Ejemplo 30

Expresa el máximo común divisor de \(574\) y \(252\) como una combinación lineal entera.
Solución.
Primero usemos la Observación 2 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 sustituir 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 tendremos 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 30 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 solamente una vez. El siguiente teorema proporciona este método, que se denomina algoritmo extendido de Euclides.

Teorema 9 (Algoritmo extendido de Euclides)

Sean \(a\) y \(b\) enteros positivos. Entonces

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

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, \\ \end{align*}\]

y

\[s_j = s_{j-2} - q_{j-1}s_{j-1}, \quad t_j = t_{j-2} - q_{j-1}t_{j-1},\]

para \(j = 2,3,\ldots,n\), 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 fuerte.
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 para \(j = 1,2,\ldots ,k-1\), \(P(j)\) es verdadera, es decir que para cada valor de \(j\) se cumple que

\[r_j = s_ja + t_jb.\]

Paso inductivo. Vamos a demostrar que \(P(1),P(2),\ldots ,P(k-1)\) implican \(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, tendremos 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 31

Usa el Teorema 9 para encontrar la combinación lineal de \(574\) y \(252\) que es igual a 14$.

Solución.

Primero usaremos el algoritmo de Euclides para obtener los valores de los \(q_j\).

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

Ahora, tenemos que \(r_0 = 574\) y \(r_1 = 252\).

• Para \(j = 0\) y \(j = 1\) tenemos:

\[\begin{align*} s_0 &= 1, &\quad t_0 &= 0, \\ & \\ s_1 &= 0, &\quad t_1 &= 1. \end{align*}\]

• Para \(j = 2\) tenemos:

\[s_2 = s_0 - s_1q_1 = 1-0\cdot 2 = 1, \quad t_2 = t_0 - t_1q_1 = 0 - 1\cdot 2 = -2.\]

• Para \(j = 3\) tenemos:

\[s_3 = s_1 - s_2q_2 = 0-1\cdot 3 = -3, \quad t_3 = t_1 - t_2q_2 = 1 - (-2)\cdot 3 = 7.\]

• Para \(j = 4\) tenemos:

\[s_4 = s_2 - s_3q_3 = 1-(-3)\cdot 1 = 4, \quad t_4 = t_2 - t_3q_3 = -2 - 7\cdot 1 = -9.\]

• Para \(j = 5\) tenemos:

\[s_5 = s_3-s_4q_4 = -3 - 4\cdot 1 = -7, \quad t_5 = t_3 - t_4q_4 = 7 - (-9)\cdot 1 = 16.\]

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 usando el algoritmo extendido de Euclides

El siguiente código ocupa el Teorema 9 para expresar el máximo común divisor de dos números enteros \(a\) y \(b\) como una combinación lineal de los enteros \(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 del mcd de los enteros {num1} y {num2} es: {num1}({s[-2]}) + {num2}({t[-2]}) = {a}")

euclides_extendido_ciclos(574,252)

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

euclides_extendido_ciclos(4076,1024)

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

euclides_extendido_ciclos(65432,4567)

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

Explicación del código

En este capítulo 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 verdadera, el bloque de código dentro del bucle while se ejecuta. Una vez que se completa la ejecución del bloque de código, regresa al principio del bucle while y se evalúa nuevamente la condición. Este proceso se repite hasta que la condición sea falsa y el bloque de código no se ejecuta mas, continuando con las siguientes líneas del código fuera del bucle while.

En esta ocasión usamos el operador de comparación !=, el cual verifica si dos valores son diferentes. Es un operador de comparación que devuelve el valor True si los valores comparados son diferentes y False si son iguales. Veamos algunos ejemplos de este operador.

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 asignaciones múltiples, es decir,

a,b = x,y

En el código anterior, Python entenderá que la variable «a» es igual a «x» y la variable «b» es igual a «y». No hay un límite en las variables que podemos asignar de esta manera, sólo hay que cuidar tener la misma cantidad de variables en ambos lados del símbolo =.

Vimos cómo seleccionar un elemento de una lista. Cuando creamos una lista, los elementos dentro de esta tienen un índice, los índices de las listas comienzan con el valor cero. Por ejemplo si tuviéramos una lista con los números del 1 al 5.

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

El primer elemento de la lista que es el número \(1\) tendría el índice \(0\), el segundo elemento de la lista que es el número \(2\) tendría el índice \(1\) y así sucesivamente. Si queremos seleccionar un valor de la lista simplemente tendríamos que saber su índice y ponerlo entre corchetes enfrente de la lista, es decir lista[índice].

a = lista[2]

En el ejemplo anterior, el valor de la variable «a» sería igual a \(3\).

Sin embargo, si deseamos recorrer los elementos de una lista en orden inverso, es decir, del último al primero, podemos 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.

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

En el ejemplo anterior, el valor de la variable «a» sería igual a \(4\).

La letra f al inicio de la función print, se utiliza para indicar que se está formateando una cadena de texto 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\)). Se obtendría en la consola: “Mi nombre es Juan y tengo \(30\) años.”

Veamos cómo funciona el primer código para calcular el máximo común divisor usando el algoritmo de Euclides.

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)

1. Creamos una función llamada «algoritmo_euclides» la cual recibe como argumentos dos enteros positivos, \(a\) y \(b\).

def algoritmo_euclides(a,b):

2. Empezamos un bucle 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:

3. Mientras la condición del bucle while siga siendo verdadera, el código irá imprimiendo los pasos realizados del algoritmo de Euclides usando la forma \(a = bq + r\). Después, en cada repetición del bucle while se irán intercambiando los valores, es decir, a la variable «a» se le asigna el valor de la variable «b» y a la variable «b» se le asigna el valor del residuo de dividir «a» entre «b».

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

4. Una vez que el bucle while se detenga, el código nos mostrará el máximo común divisor de los números enteros \(a\) y \(b\).

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

Ahora, veamos cómo funciona el segundo código para expresar el máximo común divisor de los enteros \(a\) y \(b\) como una combinación lineal de los enteros \(a\) y \(b\), utilizando el algoritmo extendido de Euclides.

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 del mcd de los enteros {num1} y {num2} es: {num1}({s[-2]}) + {num2}({t[-2]}) = {a}")

1. Creamos una función llamada «euclides_extendido_ciclos» la cual recibe como argumentos dos enteros positivos, \(a\) y \(b\).

def euclides_extendido_ciclos(a,b):

2. Creamos dos variables «num1» y «num2» para guardar los valores originales de \(a\) y \(b\). Además, creamos la variable «s» la cual es una lista que tiene como elementos \(1,0\) y la variable «t» la cual es una lista que tiene como valores \(0,1\). Estos valores representan a \(s_0,s_1,t_0\) y \(t_1\) respectivamente.

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

3. Empezamos un bucle while, el cual va a repetir el bloque de código dentro de él siempre que la condición b != 0 siga siendo verdadera. Esto es, que la variable «b» sea diferente de cero.

    while b!=0:

4. Empezamos obteniendo los valores \(q_j\) y \(r_j\) para poder calcular \(s_j = s_{j-2} + q_{j-1}s_{j-1}q\) y \(t_j = t_{j-2} + q_{j-1}t_{j-1}\), en cada iteración.
   Creamos la variable «q» que tiene como valor la parte entera de dividir «a» entre «b» y la variable «r» que es el residuo de dividir «a» entre «b».
   Calculamos el valor de \(s_j\) y \(t_j\) guardando éste en las variables «nuevo_s» y «nuevo_t», luego agregamos estos valores en las listas «s» y «t». Después de esta primera ejecución del bucle while, se actualizan los valores de las variables «a» y «b», es decir, a la variable «a» se le asigna el valor de la variable «b» y a la variable «b» se le asigna el valor de la variable «r», y se vuelve a repetir el bucle.

        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

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

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

Ejercicios de práctica

1. Sean \(a,b,c\) y \(d\) cualesquiera enteros positivos. Demuestra la siguientes propiedades.

   • \((ac,bc)=c\cdot (a,b)\).

   • Si \((a,b)=1\), entonces \((a+b,a-b)=1 \text{ o } 2\).

   • Si \((a,b)=d\), entonces \((a+b,a-b)=d o 2d\).

2. Encuentra el máximo común divisor de \(a+b\) y \(a^2-b^2\), donde \(a>b\).

3. Encuentra el máximo común divisor de los siguientes números:

   • \((12,18,28,38,44)\)

   • \((a^2b,ab^3,a^2b^2,a^3b^4,ab^4)\), para \(a\) y \(b\) números primos.

4. Para cada inciso, usa el algoritmo de Euclides para calcular el máximo común divisor de los números dados y luego expresa a éste como una combinación lineal de los propios números.

   • \(1024,1000\)

   • \(2076,1076\)

   • \(3076,1876\)

5. 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\).

6. 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)}\).