¡Esta es una revisión vieja del documento!
Si queremos el máximo común divisor (mcd) entre A y B (digamos que A≥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á ⇒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),…. 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.
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 A?
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).