El algoritmo de Euclides sirve para obtener el máximo común divisor de dos números enteros positivos. Es uno de los algoritmos típicos que los profesores de programación ponen a sus alumnos para practicar el bucle repetir-mientras pasando valores de una iteración a otra del bucle.

El máximo común divisor de dos números enteros positivos a y b es otro número entero positivo c tal que si dividimos a/c y b/c, los restos de las divisiones son 0, y además no existe otro número mayor que c que tenga esta caracterísitica.

El algoritmo de Euclides es el siguiente. Siendo a y b dos enteros positivos tales que a>b, comenzamos dividiendo a/b, con lo que obtendremos un resto r₁ y un cociente q₁

a=q₁·b+r₁

A partir de aquí, repetimos el siguiente proceso:

• dividir el dividendo del paso anterior entre el resto del paso anterior
• despreciar el cociente
• si el resto es 0, el mcd es el divisor de esta operacion, es decir, el último resto no nulo (recordemos que el divisor de esta operación fué el resto en la anterior.
• Si el resto no es 0, ir al primer paso

Siguiendo con el ejemplo, en la segunda iteración, dividiríamos b/r₁ obteniendo un resto r₂

b=q₂·r₁+r₂

En la tercera iteración, dividimos r_1/r₂ obteniendo un resto r3

r₁=q₃·r₂+r₃

Y se continúa así hasta obtener un resto 0. El último resto r_k distinto de cero es el mcd.

r_k-2=qk·r_k-1+r_k
r_k-1=q_k+1·r_k+0

r_k es el mcd(a,b)

Como comentábamos al principio, es muy sencillo implementarlo iterativamente. Basta tener en cuenta que en cada vuelta del bucle, y siempre a partir de la segunda iteración hay que hacer que el divisor sea el resto de la iteración anterior y el dividendo sea el divisor de la iteración anterior.

Observa este código en C#

 
static int EuclidesMCD(int a, int b) {
   int iaux; //auxiliar
   a = Math.Abs(a); //tomamos valor absoluto
   b = Math.Abs(b);
   int i1=Math.Max(a,b); //i1 = el más grande
   int i2=Math.Min(a,b); //i2 = el más pequeño
   do
   {
      iaux = i2;  //guardar divisor
      i2 = i1 % i2; //resto pasa a divisor
      i1 = iaux;  //divisor pasa a dividendo
   } while (i2 != 0);
   return i1; //ultimo resto no nulo
}
 

Muy relacionado con el máximo común divisor está el mínimo común múltiplo (mcm).

El mcm de dos enteros positivos a y b es un valor c entero y positivo tal que al dividir c/a y c/b el resto es 0, y además no existe otro número menor que c que cumpla esta condición.

Hay una relación entre mcm y mcd:

mcm(a,b)=(a·b)/mcd(a,b)

Así pues, también podemos obtener el mcm mediante el algoritmo de Euclides.

 
static int EuclidesMCM(int a, int b)
{
    return (a / EuclidesMCD(a, b)) * b;
}
 

NOTA: Observa que primero se divide a entre el mcd, en lugar de multiplicar a*b. Esto se hace para evitar un posible desbordamiento al multiplicar a*b.

Puedes probar el resultado del algoritmo de Euclides con esta minidemo: