El algoritmo de Euclides es un conocido algoritmo para calcular el máximo común divisor de dos números. Se basa en la siguiente propiedad: $\text{mcd}(a, b) = \text{mcd}(a-b, b)$. Así, si se va sustrayendo el número menor de el número mayor, cada vez los pares de números que quedan se van haciendo más pequeños hasta que uno de los números es $0$, y $\text{mcd}(a, 0) = a$.
Por ejemplo, para calcular el máximo común divisor de $105$ y $70$:
\[ \text{mcd}(105, 70) = \text{mcd}(105-70, 70) = \text{mcd}(35, 70) = \text{mcd}(35, 70-35) = \text{mcd}(35, 35) = \text{mcd}(35, 35-35) = \text{mcd}(35, 0) = 35 \]
Se puede programar de forma muy sencilla utilizando recursividad:
int mcd(int a, int b) {
if(b == 0) return a;
return mcd(b, a%b);
}
def gcd(a, b):
if b == 0: return a
return gcd(b, a%b)
La función retorna el máximo común divisor de $a$ y $b$. Si $b$ es $0$, el resultado es $a$; si no, la función se llama recursivamente con un valor de $b$ estrictamente menor (de esa forma la recursividad acabará llegando a un final). Aquí hemos utilizado el operador módulo (%), que da el resto de a cuando se divide por $b$. Esto es porque tras restar $b$ de $a$ tantas veces como sea necesario para que el resultado sea menor que $a$, lo que queda es el resto de dividir a entre $b$. Nótese que si llamamos a la función con $b > a$, en la primera llamada recursiva se intercambiarán los dos valores y se calculará el $\text{mcd}$ correctamente.