El algoritmo de Euclides

Hoy toca aprender cómo calcular el máximo común divisor de dos números muy grandes, algo que estoy seguro muchos os preguntáis varias veces a lo largo del día xD Bueno, pues yo sí que me lo he preguntado alguna vez, y cuando lo descubrí me quedé así --> :O

Un máximo común divisor (MCD) de dos números, es el divisor más alto entre esos números que no deja resto.

Por ejemplo, calculemos el MCD de 12 y 18:

Los divisores de 12 son {1, 2, 3, 4, 6, 12} y los de 18 son {1, 2, 3, 6, 9, 18}. Se ve claramente que ambos números compartes varios divisores, como son {1, 2, 3, 6}, de los cuales el mayor es 6. Por lo tanto, el MCD de 12 y 18 es 6.

El cálculo del MCD es una tarea muy sencilla, el problema es que cuando queremos encontrar los divisores de números muy altos se vuelve en algo un poco cansino... ¿alguien se anima a decirme todos los divisores de 3452 y 342 para luego buscar el mayor de todos los que coincidan? Poder se puede, pero tardaríamos una barbaridad.

(Nota: hay otra forma para calcular el MCD para números algo mayores que 12 y 18, pero sigue siendo cansino y a la vez complicado para números muy grandes. Aquí un vídeo con un ejemplo).

El algoritmo de Euclides es un método rápido y a la vez sencillo para calcular el MCD de dos números grandes. Allá vamos… o no. Antes hay que aclarar un par de cosas básicas que seguramente todos sabréis pero que no está mal recordar, por si las moscas:

(Sí, lo he hecho con el Paintbrush)

Ahora sí, allá vamos. Que no os asuste ese enunciado, porque es una tontería:

Teorema:

El MCD de dos números a y b siendo a>b>0 será el mismo que el MCD de b y r, donde r es el resto que obtenemos de la división a/b.

O lo que es igual pero más gráfico:

MCD{a,b}=MCD{b,r}, siendo a y b números enteros y r el resto resultante de la división entre ambos.

Como siempre, lo más fácil es entenderlo con un ejemplo:

¿Cuál es el MCD de 2366 y 273?

Según el teorema de antes, el MCD de 2366 y 273 será el mismo que el de 273 y 182. Sigamos

Y el MCD de 273 y 182 será el mismo que el de 182 y 91:

Y finalmente, el MCD de 182 y 91 será el mismo que el de 91 y 0.

Así que esto es lo que tenemos:

MCD{2366,273}=MCD{273,182}=MCD{182,91}=MCD{91,0}=91

Si hubiésemos intentado calcular el MCD con el primer método, nos habría llevado muchísimo tiempo, pero de esta forma lo hemos conseguido en escasos minutos.

Y hasta aquí llega la clase de cómo calcular el MCD de dos números mediante el algoritmo de Euclides, ahora podréis salir a la calle tranquilos =)