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:
- 1) 53.667 = 25.527 × 2 + 2.613 (divido el numero mayor con el número menor)
- 2) 25.527 = 2.613 × 9 + 2.010 (divido el número menor al resto de la operación antes mencionada)
- 3) 2.613 = 2.010 × 1 + 603 (divido el resto de la primer operación con el resto de la segunda operación)
- 4) 2.010 = 603 × 3 + 201 (divido el resto de la segunda operación con el resto de la tercera operación)
- 5) 603 = 201 × 3 (divide el resto de la tercera operación con el resto de la cuarta operación); en este momento, porque no hay resto, paramos, 201 es el numero buscado.
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):
- 1) 87 = 41 × 2 + 5 (divido el numero mayor al número menor)
- 2) 41 = 5 × 8 + 1 (divido el número menor al resto de la operación antes mencionada)
- 3) 5 = 5 × 1 (divido el resto de la primer operación con el resto de la segunda operación, que es uno, la operación no tendrá resto)
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.