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\ne 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,\text{con}0\le r<b.$$

Luego, como $b$ y $r$ son enteros, también existen $q_1$ y $r_1$ tales que $$b=r{q}_1+r_1,\text{con}0\le r_1<r.$$

Y como $r$ y $r_1$ son enteros, existen $q_2$ y $r_2\in {\mathbb{Z}}^{+}$ tales que $$r=r_1{q}_2+r_2,\text{con}0\le r_2<r_1.$$

Se puede continuar así sucesivamente. Pero este procedimiento debe de terminar, pues tenemos $b>r>r_1>r_2>\dots \ge 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},\text{con}0\le 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,\text{con}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,0\le 3068<3456.$$
Aplicando nuevamente el algoritmo de la división, obtenemos
$$3456=3068\cdot 1+388,0\le 388<3068.$$
Aplicando una vez más el algoritmo de la división, se tiene
$$3068=388\cdot 7+352,0\le 352<388.$$
Siguiendo este procedimiento,
$$388=352\cdot 1+36,0\le 36<352.$$
$$352=36\cdot 9+28,0\le 28<36.$$
$$36=28\cdot 1+8,0\le 8<28.$$
$$28=8\cdot 3+4,0\le 4<8.$$
$$8=4\cdot 2+0.$$

Como el último residuo no cero es $4$, entonces $(6524,3456)=4$.

$\mathrm{△}$

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,0\le 10<45.$$
$$45=10\cdot 4+5,0\le 5<10.$$
$$10=5\cdot 2+0.$$

Notemos que el último residuo no cero es $5$. Por lo tanto, $(-100,45)=5.$

$\mathrm{△}$

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.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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\ge b$. Usando el algoritmo de la división, definimos sucesivamente los números $r_0,r_1,\dots ,r_i$ y $q_0,q_1,\dots ,q_i$ de manera que se cumpla

$$\begin{array}{r}b=a{q}_0+r_0\\ a=r_0{q}_1+r_1\end{array}$$

con $0\le r_0<a$, y $0\le r_1<r_0$ y para $j=2,\dots ,i$ que se cumpla

$$\begin{array}{r}{r}_{j-2}=r_{j-1}{q}_j+r_j,\end{array}$$

con $0\le r_j<r_{j-1}.$

Como $b\ge a>r_0>r_1>r_2>\dots >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)=\dots =(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$.

$\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/14.0.0/svg/25fb.svg">}$

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,0\le 3068<3456.$$
$$3456=3068\cdot 1+388,0\le 388<3068.$$
$$3068=388\cdot 7+352,0\le 352<388.$$
$$388=352\cdot 1+36,0\le 36<352.$$
$$352=36\cdot 9+28,0\le 28<36.$$
$$36=28\cdot 1+8,0\le 8<28.$$
$$28=8\cdot 3+4,0\le 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{-}\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{-}\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{-}\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.

1. 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.
   1. $15$ y $35$
   2. $18$ y $92$
   3. $201$ y $153$
   4. $328$ y $528$
2. ¿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.
3. 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,\dots ,p_k$ en su factorización en primos (quizás con exponente cero). Esto nos permite escribirlos como:
   $$\begin{array}{r}m=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\dots p_k^{{\alpha }_k}\\ n=p_1^{{\beta }_1}{p}_2^{{\beta }_2}\dots p_k^{{\beta }_k}\end{array}$$.
   1. 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)}$.
   2. 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)}.$$
4. 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$.
5. 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»