Procedimiento iterativo de división que calcula el máximo común divisor (mcd) de dos enteros reemplazando repetidamente el mayor por el resto de su división por el menor hasta que el resto sea cero.

Principio

mcd(a,b) = mcd(b, a mod b); la aplicación repetida de esta reducción disminuye el tamaño de los operandos y termina en el mcd cuando un resto se vuelve cero.

Demostración

Calcular mcd(48, 18): 48 = 2·18 + 12, 18 = 1·12 + 6, 12 = 2·6 + 0, por tanto mcd(48,18) = 6. El algoritmo extendido da coeficientes x,y con 48x + 18y = 6.

Aplicación incorrecta

Aplicar el algoritmo a no enteros sin una estructura de división euclidiana o suponer tiempo constante de ejecución independientemente del tamaño de los operandos son usos indebidos habituales; también hay que manejar correctamente entradas negativas o nulas.

Consecuencia

El algoritmo de Euclides ofrece un método eficiente para calcular el mcd, fundamenta el cálculo de inversos modulares y coeficientes de Bézout mediante el algoritmo extendido, y se generaliza a dominios euclidianos.

Inversión

Usar factorización prima para hallar el mcd es el enfoque inverso; la factorización da el mcd pero suele ser mucho menos eficiente para enteros grandes que la reducción euclidiana.

Límite

Se aplica a enteros y a cualquier dominio euclidiano con un algoritmo de división con resto; no se aplica directamente a anillos arbitrarios sin norma euclidiana ni a objetos sin operación de resto bien definida.

Tensión semántica

Contrastar el algoritmo de Euclides con algoritmos binarios de mcd y con métodos basados en factorización: Euclides minimiza restos por división, los binarios explotan la aritmética binaria y la factorización depende de la descomposición en primos.

Síntesis

El algoritmo de Euclides reduce sistemáticamente un problema de mcd mediante divisiones sucesivas hasta la terminación, ofreciendo un procedimiento eficiente y generalizable que además produce combinaciones lineales que expresan el mcd.