¿Cómo calcular el máximo divisor común?

Más sobre el máximo común divisor (a veces también denominado máximo común divisor) : El máximo común divisor (MCD) entre dos números enteros positivos \(n_1\) y \(n_2\) es el mayor entero que divide tanto a \(n_1\) como a \(n_2\). Por lo general, es fácil de encontrar mediante inspección (es decir, probando muchos números de manera sistemática hasta que lo encontramos), pero eso es cierto solo para números pequeños. Calcular el GCD para grandes cantidades mediante inspección puede ser tedioso o sencillo.

Afortunadamente, existe una forma sistemática y fácil (toser, toser) de calcular el GCD para dos números. El método es así

• Calcule el descomposición prima de \(n_1\) y \(n_2\). Simbólicamente, tendríamos algo como esto: \[n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}\] \[n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}\]
• Encuentra la lista de primos comunes en la descomposición de primos correspondiente. Si no hay primos comunes, entonces DETÉNGASE, ha encontrado que GCD = 1. De lo contrario, deje que \(\{r_1, ..., r_k \}\) sea la lista de primos comunes \(k\) y deje \(\alpha_{i_l}, \beta_{i_l}\) para \(l=1,2,..,k\) los exponentes correspondientes encontrados en la descomposición prima de \(n_1\) y \(n_2\) para el común correspondiente primos.
  
  
• El GCD se calcula como: \[GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}} \]

¿El método anterior parece demasiado complejo? Realmente no. Veamos un ejemplo: calculemos el GCD para \(n_1 = 165\) y \(n_2 = 1575\). Encontremos la descomposición prima de cada uno de estos números (puede usar nuestra calculadora de descomposición prima)

\[165 = 3 \cdot 5 \cdot 11\] \[1575 = 3^2 \cdot 5^2 \cdot 7\]

De lo anterior: ¿qué números primos tienen en común estos dos números? Como podemos ver, los números primos comunes son 3 y 5. Mirando los exponentes de estos números primos comunes en cada uno de los números, buscamos el mínimo entre los dos. En este caso, el exponente mínimo para 3 es 1 y el exponente mínimo para 5 también es 1. Por lo tanto

\[GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15 \]

Aparte de la calculadora GDC, puede elegir entre nuestra selección de calculadoras y calculadoras de álgebra .