Algoritmo de Euclides
Es un algoritmo que se encuentre en uno de los Elementos de Euclides (Libros que lo hicieron famoso), más específicamente el Libro 7, proposición 2 que dice: "Dados dos números no primos entre sí, hallar su medida común máxima".
El algoritmo permite hallar la medida común máxima para dos longitudes distintas y no primas entre sí, que es lo que ahora se conoce como obtener el MCD(máximo común divisor).
¿Cómo funciona?
Partamos del hecho que queremos encontrar un segmente con el que podamos medir otros dos segmentos al mismo tiempo (imagínate que con una regla puedes medir exactamente la longitud de un televisor y una nevera, lo que queremos encontrar es la longitud de la regla)
Básicamente el proceso se describe así:
Hay dos segmentos: el A y el B, queremos encontrar un segmento X que mida exactamente a A y a B.
lo que hacemos es medir cuantas veces cabe el segmento A en el B o viceversa (depende de quien sea mayor) si no lo mide exactamente va a sobrar algún "pedazo" de segmento que llamaremos C,
Luego tenemos que ver cuantas veces cabe C en B, si lo mide completamente C es la medida común máxima de ambos segmentos, si no el proceso continua, a continuación se muestra una representación del proceso.
