Algoritmo de Euclides

En matemáticas, el algoritmo de Euclides, o algoritmo euclidiano, es un método eficiente para calcular el máximo común divisor (MCD) de dos números enteros, el número más grande que los divide a ambos sin dejar resto. Lleva el nombre del antiguo matemático griego Euclides, quien lo describió por primera vez en Elementos (ca. 300 a. C.). Es un ejemplo de un algoritmo, un procedimiento paso a paso para realizar un cálculo de acuerdo con reglas bien definidas, y es uno de los algoritmos más antiguos que se siguen utilizando. Se puede usar para reducir fracciones a su forma más simple y es parte de muchos otros cálculos teórico-numéricos y criptográficos.

El algoritmo euclidiano se basa en el principio de que el máximo común divisor de dos números no cambia si el número más grande se reemplaza por su diferencia con el número más pequeño. Por ejemplo, 21 es el MCD de 252 y 105 (ya que 252 = 21 × 12 y 105 = 21 × 5), y el mismo número 21 también es el MCD de 105 y 252 − 105 = 147. Dado que este reemplazo reduce el más grande de los dos números, al repetir este proceso se obtienen pares de números sucesivamente más pequeños hasta que los dos números se vuelven iguales. Cuando eso ocurre, son el MCD de los dos números originales. Al invertir los pasos o usar el algoritmo de Euclides extendido, el MCD se puede expresar como una combinación lineal de los dos números originales, es decir, la suma de los dos números, cada uno multiplicado por un número entero (por ejemplo, 21 = 5 × 105 + (−2) × 252). El hecho de que el MCD siempre se pueda expresar de esta manera se conoce como la identidad de Bézout.

La versión del algoritmo euclidiano descrita anteriormente (y por Euclides) puede requerir muchos pasos de resta para encontrar el MCD cuando uno de los números dados es mucho más grande que el otro. Una versión más eficiente del algoritmo acorta estos pasos, en su lugar se reemplaza el más grande de los números por su resto al dividirlo por el más pequeño de los dos (con esta versión, el algoritmo se detiene al alcanzar un resto cero). Con esta mejora, el algoritmo nunca requiere más pasos que cinco veces el número de dígitos (base 10) del número entero más pequeño. Esto fue demostrado por Gabriel Lamé en 1844 (teorema de Lamé),^[1]​^[2]​ y marca el comienzo de la teoría de la complejidad informática. Se desarrollaron métodos adicionales para mejorar la eficiencia del algoritmo en el siglo XX.

El algoritmo euclidiano tiene muchas aplicaciones teóricas y prácticas. Se utiliza para reducir fracciones a su forma más simple y para realizar divisiones en aritmética modular. Los cálculos que utilizan este algoritmo forman parte de los protocolos criptográficos que se usan para proteger las comunicaciones de Internet, y en los métodos para romper estos sistemas criptográficos mediante la factorización de grandes números compuestos. El algoritmo euclidiano se puede usar para resolver ecuaciones diofánticas, como encontrar números que satisfagan múltiples congruencias de acuerdo con el teorema chino del resto, para construir fracciones continuas y para encontrar aproximaciones racionales precisas a números reales. Finalmente, se puede utilizar como una herramienta básica para demostrar teoremas en la teoría de números, como el teorema de los cuatro cuadrados de Lagrange y la unicidad de las factorizaciones primas.

1. ↑ Lamé, Gabriel (1844). «Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers». Actas de las sesiones de la Academia de Ciencias (en francés) 19: 867-870. 
2. ↑ Ballester Niebla, Claudia (2017). Números primos. Algunas cuestiones históricas, polinomios ciclotómicos y tests de primalidad.. Universidad de La Laguna. Consultado el 4 de julio de 2023.