El algoritmo de Euclides para números grandes, método para cálcular el MCD y MCM

Identifica el máximo común divisor (mcd) de números grandes


Para números grandes, la descomposición en factores primos es difícil. Para identificar el máximo común divisor (mcd) de este tipo de números grandes, se tiene que utilizar un método que no usa la descomposición en factores primos, pero se va a utilizar el algoritmo de Euclides... vea el siguiente ejemplo.

Vamos a ver cuál es el máximo común divisor (mcd) de los números 53.667 y 25.527:

En conclusión el máximo común divisor de los dos números es el último resto (distinto de cero, por supuesto).

Si este ultimo resto es igual a uno, entonces los dos números son primos entre ellos.

Para las operaciones antes mencionados, el ultimo divisor, 201 es el máximo común divisor (mcd) de los números 53.667 y 25.527.

Podemos demonstrar usando el algoritmo de Euclides y el hecho de que dos números son primos entre ellos.

Por ejemplo, vamos a identificar mcd (87, 41):

El ultimo resto diferente de cero de las operaciones antes mencionadas es igual a 1.

mcd (87, 41) = 1, resulta que los números son primos entre ellos.

Aplicación del algoritmo de Euclides para más de dos números:

El algoritmo de Euclides se puede utilizar también para averiguar el máximo común divisor (mcd) de mas números, por ejemplo a, b și c. Se procederá en etapas. Al principio identificamos mcd (a, b) = d y después identificamos mcd (c, d) = e.

Algoritmo de Euclides: identifica el mínimo común múltiplo (mcm) para números grandes


En caso de números grandes es difícil calcular el mínimo común múltiplo (mcm), porque se necesita mucho tiempo para realizar la descomposición en factores primos.

Con la ayuda del algoritmo de Euclides identifica el máximo común divisor (mcd) – mira detrás, pero también el mínimo común múltiplo (mcm), con la regla siguiente:

mcm (a, b) = (a × b) / mcd(a, b);

No se puede utilizar este método con más de dos números.


¿Qué es un número primo?

¿Qué es un número compuesto?

Números primos hasta 1.000

Números primos hasta 10.000

Criba de Eratóstenes

Algoritmo de Euclides

Simplificar (reducir) fracciones matemáticas a sus equivalentes irreducibles: pasos a seguir y ejemplos