Una variante del algoritmo de Euclides que, dadas dos enteras a y b, calcula su máximo común divisor g y también devuelve enteros x e y tales que ax + by = g (coeficientes de Bézout).

Principio

Aplicar iterativamente la división entera con resto mientras se propagan coeficientes de combinación lineal para que en cada paso el resto actual se mantenga como una combinación entera explícita de las entradas originales.

Demostración

Calcular gcd(240, 46): las divisiones sucesivas y la retro-substitución dan 240·(−9) + 46·47 = 2, por tanto g = 2 y los coeficientes x = −9, y = 47 expresan el gcd como combinación lineal.

Aplicación incorrecta

Usarlo sin crítica sobre entradas no enteras o en estructuras sin una división euclidiana bien definida produce coeficientes sin sentido; otro uso indebido es suponer que los coeficientes devueltos son únicamente los de menor norma sin considerar las unidades.

Consecuencia

Cuando se aplica correctamente a enteros, proporciona coeficientes de Bézout, permite calcular inversos modulares si gcd = 1 y da un método constructivo para resolver ecuaciones diofánticas lineales y para estudiar ideales en dominios principales.

Inversión

El algoritmo de Euclides simple que solo devuelve el gcd sin rastrear la actualización de coeficientes; invertir la variante extendida equivale a eliminar la propagación de coeficientes y perder la información de combinación lineal.

Límite

Definido para enteros y, más generalmente, en dominios euclidianos o dominios principales con una división euclidiana significativa; no se aplica directamente a anillos conmutativos arbitrarios sin división euclidiana ni a números reales/complejos sin adaptar a una noción analítica de división.

Tensión semántica

Compite con métodos de exponentiación modular para calcular inversos en contextos computacionales (que dependen de propiedades de grupos) y con métodos de álgebra lineal para resolver ecuaciones; el algoritmo extendido es exacto y discreto, mientras que alternativas pueden ser aproximadas o requerir estructura de cuerpo.

Síntesis

Extensión constructiva del procedimiento euclidiano que conserva en cada paso coeficientes enteros explícitos que relacionan los restos con las entradas, proporcionando tanto el mcd como los coeficientes de Bézout útiles para inversos y soluciones diofánticas.