Un procedimiento iterativo basado en divisiones que calcula el máximo común divisor (mcd) de dos elementos en un dominio euclidiano (o en cualquier anillo con una función euclidiana adecuada) mediante la toma repetida de restos hasta terminar en cero.

Principio

Usar la división con resto para producir una sucesión estrictamente decreciente de normas euclidianas; la terminación da el último resto no nulo como mcd, y la retro-sustitución produce coeficientes de Bézout cuando procede.

Demostración

Ejemplo entero: mcd(1071,462). Cálculos: 1071 = 462·2 + 147, 462 = 147·3 + 21, 147 = 21·7 + 0; el último resto no nulo es 21, por tanto mcd(1071,462)=21. El algoritmo extendido produce enteros x,y con 1071x+462y=21.

Aplicación incorrecta

Aplicar el algoritmo de división en anillos sin función euclidiana o suponer que el algoritmo ofrece mcd únicos en anillos sin propiedades de norma apropiadas; también suponer la terminación sin verificar una medida estrictamente decreciente.

Consecuencia

Proporciona un método efectivo para calcular mcd, determinar invertibilidad módulo un elemento y producir representaciones de Bézout mediante el algoritmo extendido; sustenta inversos modulares y muchos procedimientos algorítmicos en teoría de números.

Inversión

En lugar de reducir mediante restos, se puede sintetizar un mcd factorizando ambos elementos e intersectando los multiconjuntos de factores; esta inversión cambia la reducción iterativa por un análisis factorial global.

Límite

Válido en dominios euclidianos (p. ej. Z, F[x]) o en entornos con una valuation euclidiana; excluye anillos sin algoritmo de división ni norma bien fundada y requiere ajustes (pseudo-división) sobre anillos de coeficientes generales.

Tensión semántica

A veces se confunde con construcciones de mcd más generales (mcd ideal-teórico, algoritmos de subresultantes) o con variantes extendidas frente a clásicas; hay tensión entre usarlo para mcd algebraicos exactos o para aproximaciones numéricas.

Síntesis

El algoritmo euclidiano es el procedimiento de divisiones repetidas con resto guiado por una valoración euclidiana; termina en número finito de pasos para producir el mcd y, por retro-sustitución, coeficientes de Bézout cuando el dominio lo permite.