Seguro que muchos de vosotros conocéis el algoritmo de Euclides para el cálculo del máximo común divisor de dos números naturales. Y seguro que recordáis el post que acabo de enlazar, donde os explicaba cómo aplicarlo.
Pero también estoy seguro de que nunca lo habéis visto, digamos, de forma visual. Es decir, con alguna especie de gráfico que lleve implícito el algoritmo y que a partir de dos números naturales termine dándonos cuál es el máximo común divisor de esos números. Y eso mismo es lo que vi hace unos días en la cuenta de Twitter @MathUpdate (muy recomendable, por cierto). Se trata de este applet de GeoGebra que está subido en GeoGebraTube. El punto azul (que se puede mover) nos indica los dos números de los que estamos calculando el máximo común divisor. El tamaño del cuadrado de la parte inferior izquierda nos dice cuál es el máximo común divisor de ellos:
Bien, ahora la pregunta es la siguiente: ¿es esto el algoritmo de Euclides? ¿Por qué el tamaño del cuadrado de abajo a la izquierda es el máximo común divisor entre esos números? Vamos a verlo.
Para comenzar, sí, esto es el algoritmo de Euclides, aunque no lo parezca. El porqué de que el máximo común divisor sea el cuadrado inferior izquierdo lo vamos a ver con un ejemplo. Para ello debemos recordar el algoritmo de Euclides que expliqué en el post que enlazo al principio de este artículo.
Vamos a calcular el MCD(102,70) con el algoritmo de Euclides, e iremos viendo qué va haciendo el applet en cada caso. Comencemos:
- Marcamos el 102 en el eje X y el 70 en el eje Y.
- Dividimos 102 entre 70:
Como el cociente es 1, quitamos un cuadrado de 70×70 desde el 102 (en el eje X) hacia la izquierda. Quedaría entonces un hueco de 32×70 a la izquierda del cuadrado quitado (ya que el resto no es cero).
- Dividimos 70 entre 32:
Como el cociente es 2, quitamos dos cuadrados de 32×32 desde el 70 (en el eje Y) hacia abajo. Quedaría entonces un hueco de 32×6 debajo de lo que hemos quitado (ya que el resto sigue sin ser cero).
- Y continuamos así, alternando izquierda con abajo.
Dividimos 32 entre 6:Como el cociente es 5, quitamos cinco cuadrado de 6×6 desde el 32 (en el eje X) hacia la izquierda. Queda entonces un hueco de 2×6 a la izquierda de lo eliminado (porque el resto todavía no es cero).
- Dividimos ahora 6 entre 2:
Como el cociente es 3 quedan tres cuadrados 2×2. Y como el resto es cero no queda ningún hueco más.
Esto nos dice que MCD(102,70)=2, que es la medida del lado del último cuadrado que ha quedado en la parte inferior izquierda.
¿Conocíais esta manera de representar gráficamente el máximo común divisor? ¿Qué os ha parecido?
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
¡Fascinante! Incluso la división es gráfica: ¿cuántos cuadrados con lado «pequeño» puedo poner pegados al lado «grande»? Y así hasta que llenas del todo el cuadrado inicial.
Justo hoy tengo que explicar el algoritmo de Euclides, así que aprovecharé para mencionarlo.
Información Bitacoras.com…
Valora en Bitacoras.com: No hay resumen disponible para esta anotación…
Fascinante. Muy bueno si señor.
Hola:
¿ cómo puedo demostrar que si un número d es divisor de otros dos (b , r) , entonces d es divisor de mcd(b,r)
Hola, jmzc: Me parece que lo que preguntas se sigue de inmediato de la definición de mcd; a saber: Dados dos números enteros a y b (los puedes suponer positivos por conveniencia, aunque la definición bien vale para cualquier par, siempre que nomde ellos sea no nulo), se define su mcd como el entero d tal que: 1. d divide tanto a «a», como a «b». 2. So D’s es otro entero que divide a «a y a «b», entonces d’ divide a d. Que la definición no sea vacía y sí válida se desprende del Principio del buen orden.… Lee más »
jmzc,
Piensa en la descomposición en factores primos de b, de r, de d, y en el m.c.d(b,r) como comunes elevados al menor exponente.
[…] El algoritmo de Euclides como nunca lo habías visto gaussianos.com/el-algoritmo-de-euclides-como-nunca-lo-hab… por gabrielin hace nada […]
Esto es fascinante!
El algoritmo de euclides tiene muchas aplicaciones, por lo menos en el síntesis de análisis de filtros analógicos para sintetizar impedancias por el método de cauer se utiliza el algoritmo de euclides para el desarrollo de las fracciones continuas.
Como siempre, muy buen post profesor.
Indudablemente cuando hay factores primos medianamente grandes es mucho más efectivo que la descomposición factorial. Y es interesante por si mismo. Yo lo explicaba en 1º y 2º de ESO con creo que buenos resultados. E hice un applet de GeoGebra al respecto:
http://www.xente.mundo-r.com/ilarrosa/GeoGebra/MCM_MCD_Euclides.html
https://ggbm.at/AE7GB7F9
[…] los comentarios 1 visto 1 alma 20 El algoritmo de Euclides como nunca lo habías visto […]
[…] del anuncio de Milka Carlos Beltrán nos habla de su solución del Problema 17 de la lista de Smale El algoritmo de Euclides como nunca lo habías visto Calabaza para Halloween con […]