Contente

• Passos
• Método 1 de 2: Algoritmo do divisor
• Método 2 de 2: Fatores principais
• Pontas

O maior divisor comum (GCD) de dois inteiros é o maior inteiro que divide cada um desses números. Por exemplo, o mdc para 20 e 16 é 4 (ambos 16 e 20 têm divisores grandes, mas não são comuns - por exemplo, 8 é um divisor de 16, mas não um divisor de 20). Existe um método simples e sistemático para encontrar GCD, chamado "algoritmo de Euclides". Este artigo mostrará como encontrar o máximo divisor comum de dois inteiros.

Passos

Método 1 de 2: Algoritmo do divisor

1. 1 Omita todos os sinais negativos.
2. 2 Aprenda a terminologia: ao dividir 32 por 5,
   • 32 - dividendo
   • 5 - divisor
   • 6 - privado
   • 2 - resto
3. 3 Determine o maior dos números. Será divisível e o menor número será o divisor.
4. 4 Escreva o seguinte algoritmo: (dividendo) = (divisor) * (quociente) + (resto)
5. 5 Coloque um número maior no lugar do dividendo e um número menor no lugar do divisor.
6. 6 Descubra quantas vezes o número maior é dividido pelo menor e escreva o resultado em vez do quociente.
7. 7 Encontre o resto e escreva-o na posição apropriada no algoritmo.
8. 8 Escreva o algoritmo novamente, mas (A) escreva o divisor anterior como um novo dividendo e (B) o resto anterior como um novo divisor.
9. 9 Repita a etapa anterior até que o restante seja 0.
10. 10 O último divisor será o máximo divisor comum (GCD).
11. 11 Por exemplo, vamos encontrar o GCD para 108 e 30:
12. 12 Observe como os números 30 e 18 da primeira linha formam a segunda linha. Em seguida, 18 e 12 formam a terceira linha e 12 e 6 formam a quarta linha. Múltiplos de 3, 1, 1 e 2 não são usados. Eles representam o número de vezes que o dividendo é divisível pelo divisor e, portanto, são exclusivos para cada linha.

Método 2 de 2: Fatores principais

1. 1 Omita todos os sinais negativos.
2. 2 Encontre os fatores primos dos números. Apresente-os como mostrado na imagem.
   • Por exemplo, para 24 e 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Por exemplo, para 50 e 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 Encontre fatores primos comuns.
   • Por exemplo, para 24 e 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Por exemplo, para 50 e 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Multiplique os fatores primos comuns.
   • Para 24 e 18, multiplique 2 e 3 e pegue 6... 6 é o maior denominador comum de 24 e 18.
   • Não há nada para multiplicar por 50 e 35. 5 É o único fator primo comum e é o GCD.
5. 5 Fez!

Pontas

• Uma maneira de escrever isso é: dividendo> divisor de mod> = resto; GCD (a, b) = b se mod b = 0, e gcd (a, b) = gcd (b, a mod b) caso contrário.
• Como exemplo, vamos encontrar o GCD (-77,91). Primeiro, use 77 em vez de -77: GCD (-77,91) converte para GCD (77,91). 77 é menor que 91, então temos que trocá-los, mas considere como o algoritmo funciona se não o fizermos. Ao calcular 77 mod 91, obtemos 77 (77 = 91 x 0 + 77). Como não é zero, consideramos a situação (b, a mod b), ou seja, GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 é o resto). Não é zero, então GCD (91,77) torna-se GCD (77,14). 77 mod 14 = 7. Isso não é zero, então GCD (77,14) torna-se GCD (14,7). 14 mod 7 = 0 (desde 14/7 = 2 sem resto). Resposta: GCD (-77,91) = 7.
• O método descrito é muito útil para simplificar frações. No exemplo acima: -77/91 = -11/13, já que 7 é o maior denominador comum de -77 e 91.
• Se aeb são iguais a zero, então qualquer número diferente de zero é seu divisor, então, neste caso, não há GCD (os matemáticos simplesmente acreditam que o maior divisor comum de 0 e 0 é 0).