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 .