Algoritmo de Euclides para hallar el MCD y simplificar una fracción

Por Pablo Murillo

El algoritmo de Euclides es una forma de calcular el máximo común divisor.

Se fundamenta en que el M.C.D. del dividendo y el divisor de una división es el mismo que el M.C.D. del divisor y el resto. Eso ocurre porque siendo c divisor de a y b (dividendo y divisor) y a= b · cociente + resto, c también divide al resto.

Para calcular el M.C.D., se realizan unas divisiones basadas en la igualdad anterior. Consisten en que se divide a:b y si el resto da 0 el M.C.D. es b, y si no da 0, hay que dividir el divisor entre el resto. Si sigue sin dar 0, se divide el divisor de esa división entre su resto. Así sucesivamente hasta que el resto de 0 y b de esa última división sea el M.C.D. Según el fundamento, todos los M.C.D. serán iguales. Ejemplo:

4259 entre 738 da 5 y sobran 569.

738 entre 569 da 1 y sobran 169.

569 entre 169 da 3 y sobran 62.

169 entre 62 da 2 y sobran 45.

62 entre 45 da 1 y sobran 17.

45 entre 17 da 2 y sobran 11.

17 entre 11 da 1 y sobran 6.

11 entre 6 da 1 y sobran 5.

6 entre 5 da 1 y sobra 1.

5 entre 1 da 5 y no sobra nada.

Es decir: M.C.D. (4259, 738)= M.C.D (738, 569)= M.C.D (569, 169)=M.C.D (169, 62)=M.C.D (62, 45)=M.C.D (45, 17)=
=M.C.D (17, 11)=M.C.D (11, 6)=M.C.D (6, 5)=M.C.D (5, 1)=1

Esto significa que la fracción 4259/738 es irreducible.