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
