Algoritmo que calcula el máximo común divisor (mcd) de dos enteros y, simultáneamente, coeficientes enteros u y v tales que u·a + v·b = mcd(a,b). Es el algoritmo de Euclides ampliado para devolver los coeficientes de Bézout.

Principio

Aplicar divisiones sucesivas con resto hasta obtener un resto cero y, mediante sustitución regresiva, expresar el último resto no nulo como combinación lineal de los enteros iniciales.

Demostración

Para mcd(99,78): 99 = 78·1 + 21, 78 = 21·3 + 15, 21 = 15·1 + 6, 15 = 6·2 + 3, 6 = 3·2 + 0, por tanto mcd = 3. La sustitución regresiva da 3 = 78·14 + 99·(−11); así u = −11, v = 14 satisfacen −11·99 + 14·78 = 3.

Aplicación incorrecta

Usarlo tal cual sobre números en coma flotante o en anillos no euclidianos sin adaptación; tomar los coeficientes como únicos sin reconocer su indeterminación por múltiplos comunes.

Consecuencia

Bien aplicado, proporciona el mcd y los coeficientes de Bézout, lo que permite resolver ecuaciones diofánticas lineales, calcular inversos modulares y servir en otros algoritmos de teoría de números.

Inversión

La inversión sería intentar obtener una factorización de los operandos a partir de los coeficientes de Bézout; éstos dan relaciones lineales pero no sustituyen a los métodos de factorización.

Límite

Definido para pares en dominios de ideales principales y dominios euclidianos (enteros, polinomios univariados sobre un cuerpo). No es aplicable sin cambios a anillos no euclidianos o polinomios multivariados.

Tensión semántica

Se diferencia del algoritmo de Euclides simple que solo devuelve el mcd; lo 'extendido' enfatiza la expresión lineal explícita, lo que puede confundirse con otros métodos de cálculo de inversos en grupos multiplicativos.

Síntesis

El algoritmo euclídeo extendido es el procedimiento del mcd complementado con sustitución regresiva sistemática para obtener coeficientes de Bézout, suministrando tanto el mcd como la combinación lineal correspondiente.