ALGORITMO DE EUCLIDES

Otro método para obtener el MCD.

El máximo común divisor de dos números naturales puede obtenerse escogiendo el mayor de todos los divisores comunes. Hay un proceso más eficiente que utiliza repetidamente el algoritmo de la división. Este método se llama algoritmo de Euclides.

El algoritmo de Euclides se describe de la forma siguiente:

 Dados dos números naturales a y b, cuyo máximo común divisor se desea hallar, y asumiendo que a >= b se siguen los pasos, que para mejor comprensión ejemplificaremos.

Queremos hallar el mcd (148 , 175):

Procedimiento:

1) Dividir el mayor por el menor, y expresar esta división mediante el algoritmo de la división.

175= 148.1 + 27,

Como el resto es distinto de 0, y teniendo en cuenta la propiedad enunciada podemos escribir:

Mcd(148, 175)= mcd(148,27).

seguimos aplicando el algoritmo de la división:

148= 27 . 5 +13

Nuevamente el resto es distinto de cero y por la propiedad ya conocida podemos decir:

mcd (148,27)=mcd (27,13)

Luego, aplicando el algoritmo:

27= 13.2 + 1

Siguiendo el mismo criterio aplicado:

Mcd(27, 13)=mcd(13,1)=1

Es decir que el mcd entre dos números aplicando el algoritmo de euclides, es el último resto no nulo.

También se puede realizar mediante divisiones sucesivas, para mejor comprensión de los alumnos.

Una de sus principales ventajas es que no es necesario calcular los divisores ni los factores de los números.

Ejemplo:

Hallar el mcd(12358, 3054).

Aplicamos el algoritmo de Euclides:

12.378 = 4. 3054 + 162

  3.054 = 18. 162 + 138

     162 = 1. 138 + 24

     138 = 5. 24 + 18

       24 = 1. 18 + 6

       18 = 3. 6 + 0

Luego mcd.(12378, 3054) = 6 que es el último resto no nulo

Es posible ampliar el algoritmo de Euclides para hallar el mcd de más de dos números.  Por ejemplo si deseamos hallar el mcd entre 150, 210 y 240:

aplicamos primero el algoritmo para hallar el mcd de dos de ellos, por ejemplo de 150 y 210.

     mcd(150,210)

210= 150 . 1 + 60

150=  60 .  2 + 30

60  =  30.2 + 0

mcd(150, 210 )= 30

 Luego aplicamos el algoritmo entre el mcd hallado,30,  y el número restante.

     mcd (30, 240)

240= 30 .8 + 0

     mcd(30,240) = 30

Finalmente, el resultado obtenido es el mcd de los tres números.

      mcd (150,210,240) = 30