El Algoritmo de Euclides para números grandes, teoría

Un método para calcular (encontrar) el máximo común divisor (mcd) de números grandes

Para números grandes, el proceso de descomposición en factores primos es largo y difícil. Si necesitáramos calcular el máximo común divisor (mcd) para números tan grandes, entonces un método que no se basa en la descomposición en factores primos de los números sería más que bienvenido. El Algoritmo de Euclides es uno de esos métodos para calcular el mcd.

Veamos el ejemplo a continuación. También explicaremos por qué está funcionando.

Este algoritmo comienza dividiendo los números y registrando el resto de la operación.
Si 'a' y 'b' son los dos enteros positivos, 'a' >= 'b'.
Divide el número 'a' por el número 'b' y obtén el resto, 'r'.
Si 'r' = 0, deténgase aquí. 'b' es el mcd de 'a' y 'b'.
Si no: Reemplace ('a' por 'b') y ('b' por 'r'). Regrese al paso anterior.

[1] Comienza dividiendo el número mayor por el menor:
53.667 ÷ 25.527 = 2 y el resto = 2.613 => 53.667 = 25.527 × 2 + 2.613
[2] Luego divide el número más pequeño por el resto de la operación anterior:
25.527 ÷ 2.613 = 9 y el resto = 2.010 => 25.527 = 2.613 × 9 + 2.010
[3] Dividir el resto de la primera operación por el resto de la segunda operación:
2.613 ÷ 2.010 = 1 y el resto = 603 => 2.613 = 2.010 × 1 + 603
[4] Dividir el resto de la segunda operación por el resto de la tercera operación:
2.010 ÷ 603 = 3 y el resto = 201 => 2.010 = 603 × 3 + 201
[5] Dividir el resto de la tercera operación por el resto de la cuarta operación:
603 ÷ 201 = 3 y el resto = 0 => 603 = 201 × 3
En este paso, el resto es cero, por lo que podemos detenernos: 201 es el número que buscábamos.
Concluyendo:
201 es el último resto distinto de cero. Este es el máximo común divisor, mcd, de los números.

Si este último resto es igual a 1, entonces los dos números son primos entre sí (coprimos, primos relativos).
Para las operaciones anteriores, el último resto distinto de cero, 201, es el máximo común divisor (mcd) de los números 53.667 y 25.527.
Al usar el Algoritmo de Euclides podemos probar que dos números son primos relativos, vea el ejemplo a continuación.

[1] Comienza dividiendo el número mayor por el menor:
87 ÷ 41 = 2 y el resto = 5 => 87 = 41 &multiply; 2 + 5
[2] Luego divide el número más pequeño por el resto de la operación anterior:
41 ÷ 5 = 8 y el resto = 1 => 41 = 5 &multiply; 8 + 1
[3] Dividir el resto de la primera operación por el resto de la segunda operación:
5 ÷ 1 = 5 y el resto = 0 => 5 = 1 &multiply; 5 + 0
El último resto distinto de cero de las operaciones anteriores es igual a 1.
mcd (87, 41) = 1, por lo que los números son primos entre sí.

Nota: La división 'a' ÷ 'b' = 'q' + 'r' corresponde a la ecuación: 'a' = 'b' &multiply; 'q' + 'r', donde 'q' es el cociente de la división.
Si el último valor de 'r' = 0, entonces el último valor de 'b' es un divisor del último valor de 'a' ya que 'a' = 'b' '.$multiply .' 'q' + 0.

Calculemos el mcd (a, b):
1. Paso: 'a' = 'b' &multiply; 'q₁' + 'r₁', 'r₁' no es cero.
2. Paso: 'b' = 'r₁' &multiply; 'q₂' + 'r₂', 'r₂' no es cero.
3. Paso: 'r₁' = 'r₂' &multiply; 'q₃' + 'r₃', 'r₃' no es cero.
...
(n-3). Paso: 'r_(n-5)' = 'r_(n-4)' &multiply; 'q_(n-3)' + 'r_(n-3)', 'r_(n-3)' no es cero.
(n-2). Paso: 'r_(n-4)' = 'r_(n-3)' &multiply; 'q_(n-2)' + 'r_(n-2)', 'r_(n-2)' no es cero.
(n-1). Paso: 'r_(n-3)' = 'r_(n-2)' &multiply; 'q_(n-1)' + 'r_(n-1)', 'r_(n-1)' no es cero.
n. Paso: 'r_(n-2)' = 'r_(n-1)' &multiply; 'q_n' + 'r_n', 'r_n' es cero.
El resto es cero, así que paramos.

Si 'r_n' = 0 => según el paso con el número n: 'r_(n-1)' es un divisor de 'r_(n-2)'.
'r_(n-1)' es también el último resto distinto de cero.
Según el paso con el número (n-1): 'r_(n-1)' es un divisor de 'r_(n-1)' (el numero en si) y 'r_(n-2)', por lo que también es divisor de 'r_(n-3)'.
Según el paso con el número (n-2): 'r_(n-1)' es un divisor de 'r_(n-2)' y 'r_(n-3)', por lo que también es divisor de 'r_(n-4)'.
Según el paso con el número (n-3): 'r_(n-1)' es un divisor de 'r_(n-3)' y 'r_(n-4)', por lo que también es divisor de 'r_(n-5)'.
...
Según el paso con el número 3: 'r_(n-1)' es un divisor de 'r₃' y 'r₂', por lo que también es divisor de 'r₁'.
Según el paso con el número 2: 'r_(n-1)' es un divisor de 'r₂' y 'r₁', por lo que también es divisor de 'b'.
Según el paso con el número 1: 'r_(n-1)' es un divisor de 'r₁' y 'b', por lo que también es divisor de 'a'.

Así, acabamos de demostrar que el último resto distinto de cero de las operaciones, r_(n-1), es un divisor de 'a' y 'b'.

Como vimos anteriormente, el resto final distinto de cero divide sin resto tanto 'a' como 'b'. Llamemos a este divisor 't'.
Según el paso de división con el número 1: Si 't' es un divisor de 'a' y 'b', entonces también es divisor de 'r₁'.
Según el paso de división cone el número 2: Si 't' es un divisor de 'b' y 'r₁', entonces también es divisor de 'r₂'.
Y así sucesivamente, hasta el número de paso (n-1): Si 't' es un divisor de 'r_(n-3)' y 'r_(n-2)', entonces también es divisor de 'r_(n-1)'. Pero como calculamos anteriormente, este divisor es el último resto distinto de cero, que en nuestro caso es 'r_(n-1)'.
Entonces 't' no podría ser mayor que 'r_(n-1)' ya que tiene que ser un divisor de él.

El algoritmo de Euclides también se puede utilizar para encontrar el máximo común divisor de varios números, más de dos, como 'a', 'b' y 'c'.
Primero calcula el mcd ('a', 'b') = 'd' y luego calcula el mcd ('c', 'd').

Para números muy grandes, se vuelve poco práctico calcular el mínimo común múltiplo (mcm) porque obtener la descomposición en factores primos de esos números lleva demasiado tiempo.
Con la ayuda del algoritmo de Euclides no solo se calcula el máximo común divisor (mcd), como se ve arriba, sino también el mínimo común múltiplo (mcm), según la fórmula:
mcm ('a', 'b') = ^{('a' × 'b')} / _{mcd ('a', 'b')}
Este método se puede utilizar cuando no hay más de dos números.