El algoritmo de Euclides es un método para calcular el máximo común divisor (MCD). Fue escrito por Euclides en su obra magna Elementos.

Dicho algoritmo funciona no sólo para los números naturales, sino para cualquier conjunto en el que exista una "división con residuo". A este tipo de divisiones en la que existe residuo se les nombra divisiones euclidianas y a los conjuntos donde se puede definir dicha división se les llama dominios euclídeos. Con lo anterior podemos decir que el algoritmo de Euclides extendido es una ligera modificación del Algoritmo de Euclides que permite además expresar al máximo común divisor como una combinación lineal. Este algoritmo tiene aplicaciones en diversas áreas como álgebra, teoría de números y ciencias de la computación, entre otras.

Por ejemplo, el conjunto de los números enteros y el de los polinomios con coeficientes racionales son dominios euclídeos porque podemos definir una división con residuo.

El algoritmo de Euclides se puede representar con la siguiente proposición:

Sean $a$, $b$ enteros no nulos. Entonces $MCD(a,b) = MCD(b,r)$ donde $r$ es el único $0 < r < b$ tal que existe un entero $q$ con $a= bq + r$. Esto es, que $r$ es el resto de la división de $a$ por $b$.

Esta proposición nos indica que es igual de válido calcular el $MCD(a,b)$ que el $MCD(b,r)$, con la ventaja de que $r$ es un entero de menor tamaño que el original a. Esto es aprovechado por el algoritmo de Euclides para el cálculo del máximo común divisor de dos números enteros.

Para calcular el $mcd$ de dos enteros $a$ y $b$ (ambos $>0$, suponemos $a > b$) se definen $q_i$ y $r_i$ recursivamente mediante las ecuaciones:

$$a = bq_1 + r_1 \ \   (0<r_1<b)$$ $$b = r_1q_2 + r_2 \ \  (0<r_2<r_1)$$ $$r_1 =r _2q_3 + r_3 \ \  (0<r_3<r_2)$$ $$....$$ $$r_{k-3} = r_{k-2}q_{k-1} + r_{k-1}  \ \ (0<r_{k-1}<r_{k-2})$$ $$r_{k-2} = r_{k-1}q_k  \ \ (r_k=0)$$

Y de la proposición anterior, se sigue que:

$$MCD(a,b) = MCD(b,r_1) = MCD(r_1,r_2) = ... = MCD(r_{k-2},r_{k-1}) = r_{k-1}$$

Además se puede demostrar que el número de pasos necesarios para calcular el mcd de dos números es menor que 5 veces el número de dígitos del menor de ellos.