El algoritmo de Euclides. El máximo común divisor (mcd) de dos números enteros positivos es el número entero más grande que divide uniformemente en ambos. Por ejemplo, el máximo común divisor de 102 y 68 es 34, ya que ambos 102 y 68 son múltiplos de 34, además no hay entero grande o mayor que 34 y divida uniformemente en 102 y 68.

Podemos calcular de manera eficiente el mcd mediante la siguiente propiedad, que es válido para enteros positivos p y q:
Si p> q, el MCD de p y q es el mismo que el MCD de q y p% q.

Un método para poder desarrollar el algoritmo del mcd, es a través de una función recursiva compacta cuya secuencia de reducción podria ser el siguiente ejemplo:

mcd(1440, 408)
   mcd(408, 216)
      mcd(216, 192)
         mcd(192, 24)
            mcd(24, 0)
               return 24
            return 24
         return 24
      return 24
   return 24

A continuación el algoritmo de Euclides mcd realizado de forma recursiva en java:

int MCD_Euclides(int p, int q){
    if (q == 0){
        return p;
    }else{
        return MCD_Euclides(q, p % q);
    }
}