Archivo de la etiqueta: algoritmo de la división

Álgebra Superior II: El algoritmo de Euclides

Por Leonardo Ignacio Martínez Sandoval

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 $r a + s b$ 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 Z$ tales que podemos escribir $a = b q + r, con 0 \leq 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}, con 0 \leq r_{1} < r .$

Y como $r$ y $r_{1}$ son enteros, existen $q_{2}$ y $r_{2} \in Z^{+}$ tales que $r = r_{1} q_{2} + r_{2}, con 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} > \dots \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}, con 0 \leq r_{i - 1} < r_{i - 2} .$

Y en el último paso tendríamos $q_{i} \in Z^{+}$ y $r_{i} = 0$ tales que
$r_{i - 2} = r_{i - 1} q_{i} + 0, 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 \leq 3068 < 3456.$
Aplicando nuevamente el algoritmo de la división, obtenemos
$3456 = 3068 \cdot 1 + 388, 0 \leq 388 < 3068.$
Aplicando una vez más el algoritmo de la división, se tiene
$3068 = 388 \cdot 7 + 352, 0 \leq 352 < 388.$
Siguiendo este procedimiento,
$388 = 352 \cdot 1 + 36, 0 \leq 36 < 352.$
$352 = 36 \cdot 9 + 28, 0 \leq 28 < 36.$
$36 = 28 \cdot 1 + 8, 0 \leq 8 < 28.$
$28 = 8 \cdot 3 + 4, 0 \leq 4 < 8.$
$8 = 4 \cdot 2 + 0.$

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

$△$

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

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

$△$

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 Z^{+},$ tales que $a = b q + r .$ Entonces $(a, b) = (b, r) .$

Demostración. Sean $a, b \in 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 ∣ a$ . Además, $d ∣ b,$ por lo que $d ∣ b q$ . Así, $d ∣ a - b q = r$ . De este modo, $d$ es un divisor común de $b$ y de $r$ , de modo que $d ∣ f$ .

Por otro lado, $f ∣ b$ , de donde $f ∣ b q$ . Además, $f ∣ r$ . De este modo, $f ∣ b q + r = a$ . Concluimos entonces que $f$ es divisor común de $a$ y $b$ . Pero entonces $f ∣ 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.

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}, \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 \leq r_{0} < a$ , y $0 \leq 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 \leq r_{j} < r_{j - 1} .$

Como $b \geq 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$ .

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