Un procedimiento iterativo basado en divisiones que calcula el máximo común divisor (mcd) de dos enteros reemplazando repetidamente el número mayor por su resto al dividirlo por el menor hasta que el resto sea cero; el último resto no nulo es el mcd.

Principio

Si a y b son enteros con a = bq + r, entonces mcd(a,b) = mcd(b,r). Repetir este paso reduce la magnitud de los operandos y garantiza la terminación; la forma extendida rehace las sustituciones para obtener coeficientes de Bézout que expresan el mcd como combinación lineal entera.

Demostración

Calcular mcd(252, 198): 252 = 198·1 + 54, 198 = 54·3 + 36, 54 = 36·1 + 18, 36 = 18·2 + 0, por tanto mcd = 18. El algoritmo euclidiano extendido sigue las combinaciones para hallar x,y con 252x + 198y = 18.

Aplicación incorrecta

Usar división en coma flotante sin control exacto de restos para mcd enteros o no normalizar signos y ceros; asumir que los pasos ingenuos del algoritmo euclidiano capturan completamente los costes de complejidad para enteros muy grandes sin considerar el modelo de aritmética entera o algoritmos de multiplicación subcuadráticos.

Consecuencia

Proporciona un método eficiente y de terminación garantizada para calcular mcd, sustenta algoritmos de inversos modulares, simplificación de fracciones, cálculo de órdenes en criptografía y teoría de números, y es un bloque básico para mcd polinómicos en dominios euclidianos.

Inversión

Contrasta con algoritmos basados en sustracción repetida o el algoritmo binario de Stein: estos realizan el mismo cálculo de mcd mediante operaciones elementales distintas y pueden ser preferibles en cierto hardware o modelos de complejidad por bits.

Límite

Se aplica en dominios euclidianos donde existe un algoritmo de división con resto (enteros, polinomios univariantes sobre un cuerpo); no se aplica directamente en anillos arbitrarios sin función euclidiana, y la entrada debe evitar el caso trivial de ambos ceros.

Tensión semántica

Tensión entre el algoritmo euclidiano clásico paso a paso y las implementaciones modernas rápidas: idénticos en principio pero diferentes en complejidad al usar aritmética entera rápida o variantes subresultantes/polimiales para contextos multivariados.

Síntesis

El algoritmo euclidiano es el proceso iterativo fundamental en dominios euclidianos que reduce el cálculo del mcd a restos más pequeños, garantiza la terminación, produce representaciones de Bézout en su forma extendida y subyace a muchas construcciones básicas en teoría algorítmica de números y álgebra.