Introducción
En entradas anteriores estudiamos los conceptos de máximo común divisor y de mínimo común múltiplo. Ahora nos enfocaremos en un aspecto un poco más práctico sobre el máximo común divisor que dejamos pendiente: ¿cómo lo calculamos? Para ello hablaremos de un procedimiento conocido como el algoritmo de Euclides, el cual afirma que afirma que podemos aplicar iteradas veces el algoritmo de la división en ciertos números específicos, comenzando con dos enteros $a$ y $b$ para encontrar su máximo común divisor de dos enteros positivos $a$ y $b$.
Lo primero que haremos es explicar el procedimiento mediante el cual podemos encontrar el máximo común divisor de dos números aplicando repetidamente el algoritmo de la división. En la siguiente sección daremos la demostración de por qué funciona este procedimiento. Hacia el final de la entrada también veremos que este mismo procedimiento nos permite también escribir al máximo común divisor de dos enteros $a$ y $b$ como combinación lineal de ellos, es decir, de la forma $ra+sb$ con $r$ y $s$ números enteros.
El procedimiento del algoritmo de Euclides
Sean $a, b$ cualesquiera enteros positivos, con $a \neq b$ y $a > b.$ Por el algoritmo de la división, sabemos que siempre existen $q, r \in \mathbb{Z}$ tales que podemos escribir $$a = bq + r, \enspace \text{con} \quad \quad 0 \leq r < b. $$
Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b = rq_1 + r_1,\enspace \text{con} \quad \quad 0 \leq r_1 < r.$$
Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2 \in \mathbb{Z}^+$ tales que $$r = r_1q_2 + r_2,\enspace \text{con} \quad \quad 0 \leq r_2 < r_1.$$
Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\ldots \geq 0$, de modo que debe existir una $i$ tal que $r_i=0$. De esta forma, en el penúltimo paso tendremos que existen $q_{i-1}$ y $r_{i-1}$ enteros tales que $$r_{i-3} = r_{i-2}q_{i-1} + r_{i-1}, \enspace \text{con} \quad \quad 0 \leq r_{i-1} < r_{i-2}.$$
Y en el último paso tendríamos $q_i \in \mathbb{Z}^+$ y $r_i = 0$ tales que
$$r_{i-2} = r_{i-1}q_i + 0, \enspace \text{con} \quad \quad 0 = r_i < r_{i-1} .$$
Lo que nos dice el algoritmo de Euclides es que el último residuo no cero, en este caso $r_{i-1}$ es el máximo común divisor de $a$ y $b$.
Este procedimiento es particularmente útil cuando $a$ y $b$ son números tan grandes, tanto que determinar el máximo común divisor de ellos no sea inmediato. Aunque se comience con números muy grandes, el algoritmo de Euclides encuentra el MCD de manera rápida.
Ejemplo del algoritmo de Euclides
A continuación veremos el algoritmo de Euclides en acción.
Problema. Encuentra el máximo común divisor de $3456$ y $6524$.
Solución. Observamos que $6524 > 3456$. Así, $$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
Siguiendo este procedimiento,
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$
Como el último residuo no cero es $4$, entonces $(6524, 3456)=4$.
$\triangle$
Observación. Aunque el algoritmo de Euclides requiere que los números $a$ y $b$ sean positivos, cuando ocurre el caso de que uno de ellos o los dos fueran negativos, no hay un gran obstáculo. Basta sacar el valor absoluto de ambos números al inicio, ya que los divisores de un número negativo son los mismos que los de su valor absoluto.
Veamos un ejemplo que usa esta observación.
Ejemplo. Obtén el máximo común divisor de $-100$ y $45$.
Solución. Como uno de los números es negativo, antes que nada sacamos valores absolutos: $|-100| = 100$ y $|45| = 45.$ Le aplicamos el algoritmo de Euclides a estos números:
$$ 100 = 45 \cdot 2 + 10, \quad \quad 0 \leq 10 < 45. $$
$$ 45 = 10 \cdot 4 + 5, \quad \quad 0 \leq 5 < 10. $$
$$10 = 5 \cdot 2 + 0.$$
Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100, 45) = 5.$
$\triangle$
Demostración de la validez del algoritmo de Euclides
Ahora, veamos la demostración de que el algoritmo de Euclides funciona. El resultado clave para demostrarlo es la siguiente proposición.
Proposición. Sean $a,b \in \mathbb{Z}^+, $ tales que $a = bq + r.$ Entonces $(a,b) = (b,r).$
Demostración. Sean $a,b \in \mathbb{Z}^+$. Sea $d=(a,b)$ el máximo común divisor de $a$ y $b$, y sea $f=(b,r)$ el máximo común divisor de $b$ y $r$.
Tenemos que $d\mid a$. Además, $d \mid b,$ por lo que $d\mid bq$. Así, $d\mid a-bq=r$. De este modo, $d$ es un divisor común de $b$ y de $r$, de modo que $d\mid f$.
Por otro lado, $f\mid b$, de donde $f\mid bq$. Además, $f\mid r$. De este modo, $f\mid bq+r=a$. Concluimos entonces que $f$ es divisor común de $a$ y $b$. Pero entonces $f\mid d$.
Por propiedades de divisibilidad, tenemos entonces que $|f|=|d|$, pero como ambos son números no negativos concluimos entonces que $f=d$, como queríamos.
$\square$
Ya con este resultado demostrado, enunciemos formalmente el algoritmo de Euclides y demos su demostración.
Teorema. Empecemos tomando dos enteros positivos $a$ y $b$, con $a\geq b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\ldots,r_i$ y $q_0,q_1,\ldots,q_i$ de manera que se cumpla
\begin{align*}
b=aq_0+r_0\\
a=r_0q_1+r_1
\end{align*}
con $0\leq r_0<a$, y $0\leq r_1 < r_0$ y para $j=2,\ldots,i$ que se cumpla
\begin{align*}
r_{j-2}=r_{j-1}q_j+r_{j},
\end{align*}
con $0\leq r_j < r_{j-1}.$
Como $b\geq a > r_0 > r_1 > r_2 > \ldots > r_i$, entonces podemos suponer que $r_i=0$. Entonces $(a,b)=r_{i-1}$.
Demostración. Por la proposición anterior, tenemos que $(a,b)=(b,r_0)$. También por esa misma proposición, tenemos que $(b,r_0)=(r_0,r_1)$. Y, de hecho, aplicando repetidamente la proposición tenemos que:
$$(r_0,r_1)=(r_1,r_2)=\ldots=(r_{i-1},r_i)=(r_{i-1},0)=r_{i-1}.$$
La penúltima igualdad es porque $r_i=0$ y la última porque $(n,0)=n$ para cualquier entero positivo $n$.
$\square$
Máximo común divisor como combinación lineal entera
Una última consecuencia del algoritmo de Euclides es que nos ayuda a poner al máximo común divisor de dos números $a$ y $b$ como combinación lineal entera de ellos dos.
Una forma práctica de encontrar la combinación lineal correspondiente es mediante el siguiente procedimiento. Tomaremos como ejemplo el algoritmo de Euclides que ya habíamos hecho para encontrar $(6524,3456)$.
$$6524 = 3456\cdot 1 + 3068, \quad \quad 0 \leq 3068 < 3456. $$
$$3456 = 3068 \cdot 1 + 388, \quad \quad 0 \leq 388 < 3068. $$
$$3068 = 388\cdot 7 + 352, \quad \quad 0 \leq 352 < 388. $$
$$388 = 352 \cdot 1 + 36, \quad \quad 0 \leq 36 < 352. $$
$$352 = 36 \cdot 9 + 28, \quad \quad 0 \leq 28 < 36. $$
$$36 = 28\cdot 1 + 8, \quad \quad 0 \leq 8 < 28.$$
$$28 = 8 \cdot 3 + 4, \quad \quad 0 \leq 4 < 8.$$
$$8 = 4\cdot 2 + 0.$$
Lo que haremos es la siguiente tabla, en donde en la columna izquierda ponemos todos los residuos que vamos encontrando. Además, completaremos la primera fila con $1,0$ y la segunda con $0,1$.
| $6524$ | $1$ | $0$ |
| $3456$ | $0$ | $1$ |
| $3068$ | ||
| $388$ | ||
| $352$ | ||
| $36$ | ||
| $28$ | ||
| $8$ | ||
| $4$ |
Vamos a ir llenando la tabla con lo que ya sabemos del algoritmo de Euclides. Por el algoritmo de Euclides, sabemos que $3456$ cabe $1$ vez en $6524$. Por esta razón, restamos $1$ vez la segunda fila de la primera, para obtener $1-0=1$ y $0-1=-1$. Estos son los números que van en la fila $3$, columnas $2$ y $3$:
| $6524$ | $1$ | $0$ |
| $3456$ | $0$ | $1$ |
| $3068$ | $\mathbf{1}$ | $\mathbf{-1}$ |
| $388$ | ||
| $352$ | ||
| $36$ | ||
| $28$ | ||
| $8$ | ||
| $4$ |
De nuevo, $3068$ cabe una vez en $3456$, así que de nuevo restamos una vez el tercer renglón del segundo. Nos queda $0-1=-1$ y $1-(-1)=2$ para las nuevas entradas:
| $6524$ | $1$ | $0$ |
| $3456$ | $0$ | $1$ |
| $3068$ | $1$ | $-1$ |
| $388$ | $\mathbf{-1}$ | $\mathbf{2}$ |
| $352$ | ||
| $36$ | ||
| $28$ | ||
| $8$ | ||
| $4$ |
Ahora cambia un poco, pues $388$ ya sabemos que cabe $7$ veces en $3068$ (por lo que hicimos del algoritmo de Euclides). Así, para la nueva fila restamos siete veces la cuarta fila de la tercera, para obtener como nuevos números $1-7\cdot (-1)=8$ y $-1-7\cdot (2)=-15$. La tabla queda así:
| $6524$ | $1$ | $0$ |
| $3456$ | $0$ | $1$ |
| $3068$ | $1$ | $-1$ |
| $388$ | $-1$ | $2$ |
| $352$ | $\mathbf{8}$ | $\mathbf{-15}$ |
| $36$ | ||
| $28$ | ||
| $8$ | ||
| $4$ |
Siguiendo este procedimiento repetidamente, llegamos a la siguiente tabla:
| $6524$ | $1$ | $0$ |
| $3456$ | $0$ | $1$ |
| $3068$ | $1$ | $-1$ |
| $388$ | $-1$ | $2$ |
| $352$ | $8$ | $-15$ |
| $36$ | $-9$ | $17$ |
| $28$ | $89$ | $-168$ |
| $8$ | $-98$ | $185$ |
| $4$ | $383$ | $-723$ |
Los últimos dos números que pusimos en la tabla nos dan la respuesta de cómo poner a $4$ como combinación lineal entera de $6524$ y de $3456$:
$$4=383 \cdot 6524 – 723 \cdot 3456.$$
Verifica que en efecto las cuentas son correctas, y que esta expresión final es válida.
¿Cómo se demuestra que este procedimiento siempre funciona? Se puede mostrar inductivamente que, de hecho, para cada uno de los renglones con entradas $a,b,c$ se cumple que $a=6524b+3456c$. Esto queda como uno de los problemas de tarea moral.
Más adelante…
Esta entrada termina nuestra exploración introductoria al mundo de la aritmética de los números enteros. Sin embargo, todavía hay otros lugares a los que nos llevará el algoritmo de la división. Hasta ahora hemos discutido mucho el caso de la divisibilidad, es decir, cuando el residuo de la división de un número entre otro es igual a cero. Pero también podemos encontrar estructuras matemáticas muy ricas si estudiamos al resto de los posibles residuos. A partir de la siguiente entrada hablaremos del anillo de enteros módulo $n$, lo cual nos ayudará a formalizar estas ideas.
Tarea moral
A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.
- Usa el algoritmo de Euclides para encontrar el máximo común divisor de las siguientes parejas de números, y para escribirlo como combinación lineal entera de ellos.
- $15$ y $35$
- $18$ y $92$
- $201$ y $153$
- $328$ y $528$
- ¿Cómo usarías el algoritmo de Euclides para encontrar el máximo común divisor de los números $91$, $105$ y $119$? Es decir, debes encontrar el mayor entero $d$ que divida a estos tres números de manera simultánea.
- Hay otra forma de encontrar el máximo común divisor de dos números si conocemos su factorización en números primos. Imagina que tenemos dos números $n$ y $m$ y que, conjuntamente, usan los números primos distintos $p_1,p_2,\ldots, p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
\begin{align*} m=p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_k^{\alpha_k} \\ n=p_1^{\beta_1}p_2^{\beta_2}\ldots p_k^{\beta_k}\ \end{align*}.- Demuestra que la máxima potencia de $p_1$ que divide tanto a $m$ como a $n$ es $p_1^{\text{min}(\alpha_1,\beta_1)}$.
- Demuestra que el máximo común divisor de $m$ y $n$ es $$p_1^{\text{min}(\alpha_1,\beta_1)} p_2^{\text{min}(\alpha_2,\beta_2)}\cdots p_k^{\text{min}(\alpha_k,\beta_k)}.$$
- Demuestra un resultado análogo al del inciso anterior para el mínimo común múltiplo y usa ambos resultados para dar otra demostración de que $(m,n)[m,n]=mn$.
- Verifica que, en efecto, el método explicado en la entrada ayuda a escribir al máximo común divisor de dos enteros como combinación lineal de ellos.
Entradas relacionadas
- Ir a: Álgebra Superior II
- Entrada anterior del curso: Teorema fundamental de la aritmética e infinidad de números primos
- Siguiente entrada del curso: Problemas de divisibilidad y el algoritmo de Euclides
Agradecimientos
Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE104522 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 2»
Muy bueno el post estoy programando una encriptadora, para un proyecto de mi facultad, y me cayó de 10 este tema