##  [Algoritmo Euclidiano Extendido](/es/node/61982) 

 Definición

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

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

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

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

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

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

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

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

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.