Como calcular o maior divisor comum?

Mais sobre o maior divisor comum (às vezes também referido como o maior fator comum) : O maior divisor comum (GCD) entre dois números inteiros positivos \(n_1\) e \(n_2\) é o maior número inteiro que divide \(n_1\) e \(n_2\). Geralmente é fácil de encontrar por inspeção (isto é, tentar muitos números de maneira sistemática, até encontrá-lo), mas isso só é verdade para pequenos números. Calcular o GCD para grandes números por inspeção pode ser tedioso ou simplesmente difícil.

Felizmente, existe uma maneira sistemática e fácil (tosse, tosse) de calcular o GCD para dois números. O método é assim

• Calcule o decomposição primária de \(n_1\) e \(n_2\). Simbolicamente, teríamos algo assim: \[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}\]
• Encontre a lista de primos comuns na decomposição primo correspondente. Se não houver primos comuns, então STOP, você descobriu que GCD = 1. Caso contrário, seja \(\{r_1, ..., r_k \}\) a lista de \(k\) primos comuns e seja \(\alpha_{i_l}, \beta_{i_l}\) para \(l=1,2,..,k\) os expoentes correspondentes encontrados na decomposição primária de \(n_1\) e \(n_2\) para o comum correspondente primos.
  
  
• O GCD é calculado 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}\}} \]

O método acima parece muito complexo ?? Na verdade não. Vejamos um exemplo: vamos calcular o GCD para \(n_1 = 165\) e \(n_2 = 1575\). Vamos encontrar a decomposição primária de cada um desses números (você pode usar nossa calculadora de decomposição primária)

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

Do acima exposto: quais números primos esses dois números têm em comum? Como podemos ver, os primos comuns são 3 e 5. Olhando para os expoentes desses primos comuns em cada um dos números, vemos o mínimo entre os dois. Nesse caso, o expoente mínimo para 3 é 1, e o expoente mínimo para 5 também é 1. Portanto

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

Além da calculadora GDC, você pode escolher entre nossa seleção de calculadoras e solucionadores de álgebra .