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.

Este algoritmo implica la operación de dividir y calcular residuos.
'a' y 'b' son los dos enteros positivos, 'a' >= 'b'.
Divida 'a' por 'b' y obtenga el resto, 'r'.
Si 'r' = 0, DETÉNGASE. 'b' = el MCD de 'a' y 'b'.
De lo contrario: Reemplaza ('a' por 'b') y ('b' por 'r'). Regrese al paso de la división, arriba.

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.

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.

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.

Nota: 'a' ÷ 'b' = 'q' + 'r' es equivalente a la ecuación: 'a' = 'q' × 'b' + 'r', donde 'q' es el cociente de la operación.
Cuando el valor final de 'r' = 0, el valor final de 'b' es un divisor del valor final de 'a', ya que 'a' = 'q' × 'b' + 0.
Retroceda a través de cada uno de los pasos anteriores y analice cada ecuación, 'a' = 'q' × 'b' + 'r', y observe que en cada paso el valor final de 'b' es un divisor de cada valor de 'r' y de cada valor de 'b' y por lo tanto es un divisor de cada valor de 'a'. Entonces, el último valor de 'b', que es el último resto diferente de cero, es un divisor de los valores iniciales de 'a' y 'b'.

Mira todas las ecuaciones: 'a' = 'q' × 'b' + 'r'. Como vimos anteriormente, el valor final de 'b' es un divisor de todos los valores de 'a', 'b' y 'r'.
Por lo tanto, el valor final de 'b' también debe ser un divisor del último valor de 'r', el que es diferente de cero. Y el valor final de 'b' no podría ser mayor que el último valor de 'r'. Dado que el valor final de 'b' es igual al último valor de 'r', por lo tanto, el valor final de 'b' es el divisor más grande de los valores iniciales de ('a' y 'b'). Y, por definición, se llama el máximo común divisor de 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.

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.