OIA-Wiki

Si queremos el máximo común divisor (mcd) entre $A$ y $B$ (digamos que $A \geq B$), podemos pensar esto:

Si un número $d$ divide a $A$ y a $B$, entonces divide a la diferencia. Esto se ve ya que si $A=n*d$ y $B=m*d$, entonces $(A-B)=(n-m)*d$, que como $n$ y $m$ son enteros es múltiplo de $d$.

Entonces, si todos los divisores comunes de $A$ y $B$ dividen a la diferencia, en particular el más grande lo hará $\Rightarrow mcd(A, B) = mcd(A, A-B)$.

Ahora, qué pasa si queremos usar esto para calcular $mcd(10000, 1)$? Diríamos “bueno, eso es igual a $mcd(9999, 1)$, que es igual a $mcd(9998, 1), \ldots$. Pero eso es bastante lento. Algo que podemos pensar es que al principio, cuando tenemos $mcd(10000, 1)$, ya sabemos cuántas veces vamos a restar el 1 al número más grande. Tantas veces como pueda mientras siga siendo no negativo.

Entonces si $A=k*B+r$, con $r$ no negativo, le vamos a restar $k$ veces el número $B$ al otro número, y luego de eso nos va a quedar $r$ en vez de $A$, junto con $B$ que no lo modificamos.

Les suena la expresión $A=k*B+r$? El valor de $r$ viene a ser el resto de $A$ en la división por $B$.

Este algoritmo de ir calculando los restos y calculando el mcd de números cada vez más chicos se conoce como algoritmo de Euclides.

Un código pequeño pero muy efectivo a la hora de buscar un máximo común divisor es el siguiente:

int mcd(int a, int b){
    if(b==0){
        return a;
    }else{
        return mcd(b, a%b);
    }
}

Esto es importante para asegurarnos que este método conviene más que ir mirando los divisores de uno de los dos y ver si divide al otro.

Si tenemos los números $A$ y $B$, con $A>B$, cuánto se achica el número $A$ al reemplazarlo por $r=A\%B$?

• Si $B \gt A/2$, entonces $A=B+r$ con $r \lt A/2$
• Si $B \leq A/2$, entonces como el resto $r$ de dividir por $B$ es siempre menor que $B \Rightarrow r \leq B/2$

Entonces el número más grande será a lo sumo la mitad del más chico. Luego de un paso más, el número que no se modificó, $B$, será a lo sumo la mitad del otro, que es a lo sumo la mitad de $B$, por lo que $B$ se reemplaza por a lo sumo $B/4$.

De este razonamiento se puede ver que la complejidad es del orden del logaritmo del número más chicos de los iniciales.

Una propiedad válida para todo par de enteros $A, B$ es que $A*B = mcd(A, B)*mcm(A, B)$, donde mcm denota el mínimo común múltiplo. Entonces, una manera de calcular el mcd de dos enteros de manera rápida es hacer simplemente $mcd(A, B)=A*B/mcd(A, B)$.