El algoritmo de Euclides como nunca lo habías visto

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: 102=70 \cdot 1+32

    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: 70=32 \cdot 2 +6

    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:

    32=6 \cdot 5+2

    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: 6=2 \cdot 3+0

    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?

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

5 Comentarios

  1. ¡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.

    Publica una respuesta
  2. 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)

    Publica una respuesta
  3. 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.

    Publica una respuesta
  4. 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.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: No hay resumen disponible para esta anotación...
  2. El algoritmo de Euclides como nunca lo habías visto - [...] El algoritmo de Euclides como nunca lo habías visto gaussianos.com/el-algoritmo-de-euclides-como-nunca-lo-hab...  por gabrielin hace nada [...]
  3. El algoritmo de Euclides como nunca lo habías visto - [...] los comentarios 1 visto 1 alma 20…
  4. (Lo que yo considero) Lo mejor de 2011 en Gaussianos - Gaussianos | Gaussianos - [...] del anuncio de Milka Carlos Beltrán nos habla de su solución del Problema 17 de la lista de Smale…

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *