El Algoritmo de Euclides

Bienvenidas al Escritorio de Enrique. Antes de nada, si queréis descargaros en pdf el contenido de esta entrada podéis pinchar en este enlace post8. En este artículo (bastante más teórico que otros) vamos a tratar un tema muy relacionado con mi anterior post Congruencias. Las matemáticas de la semana: la divisibilidad de números enteros, y como tema central se estudiará el Algoritmo de Euclides (aunque realmente es anterior a Euclides) como herramienta de división de números enteros.

Dado un número entero $a$ , decimos que un entero $d$ es divisor de $a$ , o divide a $a$ si existe otro entero $b$ tal que $a = bd$ , y se escribe $d|a$ . Por ejemplo, un divisor de $12$ es $6$ , porque $12 = 2 \cdot 6$ , pues hemos encontrado un entero ( $2$ ). Llamamos máximo común divisor de dos enteros $a,\; b$ , al mayor divisor de entre todos los divisores comunes a $a$ y $b$ , y se denota por $mcd(a,\; b)$ . Por ejemplo, $mcd(24,\; 18) = 6$ . Los divisores de $24$ son $1,\; 2,\;3,\; 4,\; 6,\; 8,\; 12,\;24$ (y sus respectivos negativos), y los de $18$ son $1,\; 2,\; 3,\; 6,\; 9,\; 18$ (y sus respectivos negativos). Los divisores comunes a ambos son $1,\; 2,\; 3,\; 6$ (y sus respectivos negativos), y el mayor de todos ellos es $6$ , por lo que es el máximo común divisor.

Una forma de encontrar $mcd(a,\; b)$ es calcular «a mano» todos los divisores, como en el párrafo anterior, y quedarnos con el mayor de los comunes a ambos, pero es un método muy largo y trabajoso (hay que pensar siempre en grande, cuando tenemos números enormes). Euclides en sus Elementos expuso un algoritmo para calcular el máximo común divisor basado en la fórmula que ya comenté en el artículo que he enlazado en la introducción de $dividendo = divisor \cdot cociente\; +\; resto$ . Antes de explicarlo, vamos a realizar unas observaciones.

Si $d|ab$ , entonces $d|a$ o $d|b$ . Por ejemplo, $35 = 7 \cdot 5$ y $5|35$ , luego divide a $7$ (no) o divide a $5$ (sí). Además, si $d|a$ , entonces $d|ab$ , para cualquier entero $b$ . Por ejemplo, como $5|5$ , $5$ divide a cualquier múltiplo de $5$ ( $5k,\; \forall k \in \mathbb{Z}$ ).

El máximo común divisor de dos números es único. Esto quiere decir que no hay dos máximo común divisor diferentes. En matemáticas nada se deja a la imaginación, todo exige demostración; al fin y al cabo, a priori nada nos garantiza que esto tenga por qué ser así. La prueba es un argumento por reducción al absurdo suponiendo que existe otro máximo común divisor. Veámoslo. Sea $d$ máximo común divisor de $a$ y de $b$ (ninguno de ellos es $0$ ), y sea $c$ otro máximo común divisor. Como $d$ es máximo común divisor de $a$ y $b$ , y como $c$ es, en particular, divisor de ellos, también tiene que dividir a su máximo común divisor $d$ . Por tanto, como lo divide es porque es, como mucho, tan grande como él: $c \leq d$ . Por otra parte, podemos utilizar el mismo argumento cambiando los papeles de $c$ y $d$ , obteniendo que $d \leq c$ . De las dos desigualdades obtenemos que $c = d$ . Esto constituye un absurdo, porque habíamos supuesto que eran distintos, así que concluimos que no lo son.

Otra observación que debemos hacer es que, si $a = b + c$ y $d|a,\; d|b$ , entonces $d|c$ . La razón es que si $d|a,\; d|b$ , existen dos números $k_{1},\; k_{2}$ tales que $a = dk_{1},\; b = dk_{2}$ . Si pasamos $b$ al otro lado de la desigualdad restando, sustituimos $a$ y $b$ por sus nuevas expresiones y sacamos factor común $d$ , nos queda que $a - b = dk_{1} - dk_{2} = d(k_{1} - k_{2}) = d$ . Como $k_{1} - k_{2}$ es un número entero $k$ , concluimos que $c = dk$ . De esta forma, hemos encontrado un entero $k$ que hace que al multiplicarlo por $d$ nos dé $c$ . Por tanto, $d|c$ .

Esta última observación se puede generalizar al caso en que $a = bm + c$ y $d|a,\; d|bm.$ Así que, si dividimos $a$ entre $b$ , con la fórmula $dividendo = divisor \cdot cociente\; +\; resto$ , denotando por $c$ al cociente y $r$ al resto, la fórmula es $a = bc + r$ . Por lo que hemos descubierto hasta ahora, como $d = mcd(a,\; b)$ , en particular es un divisor de ambos, es decir, $d|a,\; d|b$ (luego $d|bc$ ). De esta forma, $d|r$ .

En matemáticas no hay una definición precisa de algoritmo, pero se podría definir como un proceso que, dados unos datos de entrada y realizando unas operaciones sistemáticas, se devuelven unos resultados de salida. El algoritmo de Euclides recibe como datos de entrada los enteros que se dividen $a,\; b$ y devuelve como salida el máximo común divisor. La clave de todo, que luego vamos a entender, es que $mcd(a,\; b) = mcd(b,\; r)$ . Veamos la forma del algoritmo:

Supongamos que $a \geq b$ (si no, intercambiamos los papeles de $a$ y $b$ ). El primer paso consiste en hacer la división de $a$ entre $b$ y escribirla en forma de $a = bc + r$ , pero vamos a llamar al cociente $c_{1}$ y al resto $r_{1}$ . Recordemos que el resto es siempre mayor o igual que $0$ y menor que el divisor.

El siguiente paso es ver si el resto es $0$ . Si lo es, entonces $a = bc_{1}$ y $b$ sería $mcd(a,\; b)$ (porque $b$ sería divisor de $a$ y no hay mayor divisor de $b$ que $b$ ). Si $r_{1} \neq 0$ , dividimos $b$ entre $r_{1}$ y lo escribimos como $b = r_{1}c_{2} + r_{2}$ . Este proceso se repite hasta encontrar un $r_{n} = 0$ , y el máximo común divisor será $r_{n-1}$ . Veámoslo bien escrito (suponiendo $a \geq b$ ):

$a = bc_{1} + r_{1}$ ( $0 \leq r_{1} < b$ )

$b = r_{1}c_{2} + r_{2}$ ( $0 \leq r_{2} < r_{1}$ )

$r_{1} = r_{2}c_{3} + r_{3}$ ( $0 \leq r_{3} < r_{2}$ )

…

$r_{n-3} = r_{n-2}c_{n-1} + r_{n-1}$ ( $0 \leq r_{n-2} < r_{n-1}$ )

$r_{n-2} = r_{n-1}c_{n}$ ( $r_{n} = 0$ )

Para comprobar que este algoritmo es correcto hay que comprobar dos cosas: que va a terminar en algún momento y que $r_{n-1} = mcd(a,\; b)$ . Pero antes vamos a ver un ejemplo.

Veamos quién es $mcd(36,\; 174)$ . Tal y como están dispuestos los números, $36$ jugaría el papel de $a$ y $174$ el de $b$ , pero como $36 < 174$ , vamos a cambiar el orden, es decir, vamos a encontrar el $mcd(174,\; 36)$ (que, obviamente, es igual).

$174 = 36 \cdot 4 + 30$ ( $c_{1} = 4,\; r_{1} = 30$ ).

Como $r_{1} \neq 0$ , $36 = 30 \cdot 1 + 6$ ( $c_{2} = 1,\; r_{2} = 6$ ).

Como $r_{2} \neq 0$ , $30 = 6 \cdot 5$ ( $c_{3} = 5,\; r_{3} = 0$ ).

$r_{3} = 0$ , luego $mcd(36,\; 174) = mcd(174,\; 36) = r_{2} = 6$ .

La justificación de la terminación del algoritmo radica en que cada $r_{i+1} < r_{i}$ y en que todos los $r_{i} \geq 0$ . Por lo que en cada iteración del algoritmo los restos se van haciendo cada vez más pequeños, hasta que no les queda otra que anularse.

Ver que $r_{n-1} = mcd(a,\; b)$ es un pelín más costoso. Por una parte hay que demostrar que $r_{n-1}$ es divisor de $a$ y $b$ , y por otra hay que demostrar que si $c$ es otro divisor común de $a$ y $b$ , entonces es más pequeño que $r_{n-1}$ .

Para ver que $r_{n-1}$ es divisor de $a$ y $b$ , comencemos por el final del algoritmo.

$r_{n-2} = r_{n-1}c_{n}$ . Esto, junto con el hecho de que $r_{n-1} < r_{n-2}$ , implica que $r_{n-1} | r_{n-2}$ .

Ahora vamos al paso justo anterior del algoritmo sabiendo que $r_{n-1} | r_{n-2}$ .

$r_{n-3} = r_{n-2}c_{n-1} + r_{n-1}$ . Como $r_{n-1}$ divide a ambos sumandos del lado derecho de la fórmula, existe $k_{1} \in \mathbb{Z}$ tal que $r_{n-3} = r_{n-1}k_{1}$ . Por tanto, $r_{n-1} | r_{n-3}$ .

Si repetimos este proceso de abajo hacia arriba del algoritmo, en el primer paso del algoritmo tendríamos que $r_{n-1}$ divide a $r_{1}$ y a $b$ , luego divide a $a$ . En conclusión: es divisor común de $a$ y $b$ .

Ahora, si suponemos que $d$ es otro divisor común de $a$ y $b$ , por el primer paso del algoritmo, también va a ser divisor de $r_{1}$ . En el segundo paso del algoritmo obtenemos que $d$ es divisor de $r_{2}$ (por serlo de $b$ y $r_{1}$ ). Reiterando el argumento hasta llegar al penúltimo paso, obtendríamos que $d$ es divisor de $r_{n-1}$ , lo que implica que $d < r_{n-1}$ y $r_{n-1} = mcd(a,\; b)$ .

Como colofón para los más teóricos vamos a demostrar el Teorema Fundamental de la Aritmética, que dice que todo número entero se descompone como producto de números primos (de manera única). Por ejemplo, $12 = 2^{2} \cdot 3$ (el primo $2$ aparece elevado al cuadrado porque se está multiplicando dos veces, luego no deja de ser un producto de números primos). La demostración es por inducción sobre el número.

Si $n = 2$ , $2$ ya es un número primo.

Sea $n > 2$ . Si $n$ es primo, ya habríamos terminado, porque la descomposición es ese mismo número. Si no es primo, entonces tiene algún divisor primo $p$ de forma que $n = kp$ . Por hipótesis de inducción, como $k < n,\; k$ se descompone en producto de números primos, $k = p_{1}p_{2} \cdots p_{i}$ , luego $n = p_{1}p_{2} \cdots p_{i}p$ .

Como véis, el algoritmo de Euclides es muy útil para calcular de forma eficiente el máximo común divisor. Espero que os haya gustado. Si es así, dejádmelo en los comentarios. ¡Hasta la próxima!

Autor: Enrique Ferres

Soy matemático por la Universidad Complutense de Madrid especializado en Ciencias de la Computación, PDI en U-tad y estudiante PhD en Didáctica de las Matemáticas en la UCM. Miembro de Scenio. También divulgo en Twitter: @enrique_ferres Lee todas las entradas de Enrique Ferres

Un comentario en “El Algoritmo de Euclides”

Pingback: Ecuaciones diofánticas y fracciones continuas – El Escritorio de Enrique

Deja una respuesta Cancelar la respuesta

Introduce aquí tu comentario...

Introduce tus datos o haz clic en un icono para iniciar sesión:

Correo electrónico (obligatorio) (La dirección no se hará pública)

Nombre (obligatorio)

Web

Estás comentando usando tu cuenta de WordPress.com. ( Salir / Cambiar )

Estás comentando usando tu cuenta de Facebook. ( Salir / Cambiar )

Cancelar

Conectando a %s

Compártelo:

Me gusta esto:

Relacionado

Autor: Enrique Ferres

Un comentario en “El Algoritmo de Euclides”

Deja una respuesta Cancelar la respuesta