Algoritmo de Euclides
El máximo común divisor de dos números se obtiene reemplazando el mayor por el resto de dividirlo entre el menor, hasta llegar a cero.
Divisiones sucesivas
Para hallar el máximo común divisor (MCD) de 252 y 105 no hace falta descomponer en factores primos. Basta dividir y quedarse con el resto:
El último resto distinto de cero, 21, es el MCD.
Por qué funciona
Si , todo número que divide a y a también divide a , y viceversa. Entonces los pares y tienen exactamente los mismos divisores comunes, y en particular el mismo máximo. Como los restos son cada vez más chicos, el proceso termina siempre.
Hay una imagen geométrica preciosa: un rectángulo de se rellena con los cuadrados más grandes posibles (dos de 105, dos de 42 y dos de 21). El lado del cuadrado más pequeño que encaja sin sobrar es el MCD.
Velocidad asombrosa
En 1844 Gabriel Lamé demostró que el número de pasos nunca supera cinco veces la cantidad de cifras del número menor; el peor caso ocurre con números de Fibonacci consecutivos. Fue uno de los primeros análisis de eficiencia de un algoritmo en la historia.
Dónde se usa hoy
- Simplificar fracciones: dividiendo entre 21.
- Criptografía: la versión extendida del algoritmo, que encuentra tales que , calcula las claves del sistema RSA que protege compras y mensajes en internet.
- Música y engranajes: ritmos euclidianos y relaciones de dientes en mecanismos.
Donald Knuth lo llamó «el abuelo de todos los algoritmos»: lleva más de 2300 años funcionando sin cambios.
Ejercicio resuelto
Un carpintero tiene dos tablas de 1071 cm y 462 cm y quiere cortarlas en trozos iguales lo más largos posible, sin desperdicio. ¿De qué largo?
Quién la creó
Euclides de Alejandría
c. 300 a. C.
El algoritmo aparece en las proposiciones 1 y 2 del libro VII de los Elementos de Euclides, escritos en Alejandría hacia el 300 a. C., aunque es probable que los matemáticos griegos anteriores, como los de la escuela de Eudoxo, ya lo conocieran. Euclides lo formuló como restas sucesivas de segmentos. En China, los Nueve capítulos describen un método equivalente para simplificar fracciones. La edición de los Elementos preparada por Teón de Alejandría, padre de Hipatia, es la base de casi todos los manuscritos griegos que se conservan.
Galería
¿Cuál es el MCD de 84 y 36?
Conexiones
Seguí el hilo
Pequeño teorema de Fermat
Si p es primo, elevar cualquier entero a la p deja el mismo resto que el número original al dividir entre p.
Antigua Grecia
Ciudades de mármol que inventaron la democracia
Hipatia de Alejandría
La filósofa que enseñó matemáticas en la ciudad del Faro
La computadora
De salas llenas de válvulas a miles de millones de transistores en un chip
Internet
La red de redes que conectó a la humanidad
Alan Turing
El padre de la computación que descifró Enigma
China imperial
Dos mil años bajo el Mandato del Cielo
Diferencia de cuadrados
La resta de dos cuadrados se factoriza como el producto de la suma por la diferencia de sus bases.
Ada Lovelace
La hija de Byron que imaginó el software un siglo antes