Calculadora de MDC (Máximo Divisor Comum)

A calculadora de MDC da Omni avalia o máximo divisor comum, também conhecido como maior divisor comum, entre dois e quinze números diferentes. Continue lendo para encontrar a resposta para a pergunta: “O que é o MDC?”, aprender sobre como calcular o MDC, incluindo a fatoração de primos ou o algoritmo de Euclides, decidir qual é o seu favorito e verificar por si mesmo que nossa calculadora pode economizar seu tempo ao lidar com números grandes!

A definição de Máximo Divisor Comum é que ele é o maior fator inteiro presente entre um conjunto de números. Também é conhecido como maior fator comum e maior divisor comum. Isso é importante em determinadas aplicações da matemática, como a simplificação de polinômios, em que muitas vezes é essencial extrair fatores comuns. Em seguida, aprenderemos como calcular o MDC.

Há vários métodos que ajudam você a calcular o MDC. Alguns deles são mais fáceis de usar, enquanto outros são mais complexos. Vale a pena conhecer todos eles para que você possa decidir qual prefere. Para calcular o MDC você pode usar:

• A lista de divisores;
• A fatoração de números primos;
• O algoritmo de Euclides;
• A busca binária (algoritmo de binário); e
• Várias propriedades do MDC (incluindo o Mínimo Múltiplo Comum, MMC).

A boa notícia é que você pode calcular o MDC com operações matemáticas simples, sem raízes ou logaritmos! Na maioria dos casos, você só precisa fazer subtração, multiplicação ou divisão.

O principal método usado para calcular o máximo divisor comum é encontrar todos os divisores dos números fornecidos. Este é um dos métodos usados pela nossa calculadora de máximo divisor comum, mas você também pode usar a calculadora de divisores da Omni para realizar essa tarefa. Os divisores, ou fatores, são simplesmente números que quando multiplicados, resultam no valor original. Em geral, eles podem ser tanto positivos quanto negativos, por exemplo, 2 ⋅ 3 é o mesmo que (-2) ⋅ (-3), ambos iguais a 6. Do ponto de vista prático, consideramos apenas os positivos. Além disso, apenas os números inteiros estão em questão. Caso contrário, você poderia encontrar uma combinação infinita de frações distintas como divisores, o que é inútil no nosso caso. Sabendo disso, calculemos o maior denominador comum dos números 72 e 40.

1. Os divisores de 72 são: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72.
2. Os divisores de 40 são: 1, 2, 4, 5, 8, 10, 20, 40.
3. Liste todos os divisores comuns: 1, 2, 4, 8.
4. O Maior Divisor Comum é 8, o maior valor acima.

Vamos tentar algo mais desafiador. Queremos encontrar a resposta para a pergunta: “Qual é o maior divisor comum de 33.264 e 35.640?” Tudo o que precisamos fazer é repetir as etapas anteriores:

1. Os divisores de 33.264 são: 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 14, 16, 18, 21, 22, 24, 27, 28, 33, 36, 42, 44, 48, 54, 56, 63, 66, 72, 77, 84, 88, 99, 108, 112, 126, 132, 144, 154, 168, 176, 189, 198, 216, 231, 252, 264, 297, 308, 336, 378, 396, 432, 462, 504, 528, 594, 616, 693, 756, 792, 924, 1.008, 1.188, 1.232, 1.386, 1.512, 1.584, 1.848, 2.079, 2.376, 2.772, 3.024, 3.696, 4.158, 4.752, 5.544, 8.316, 11.088, 16.632, 33.264.

2. Os divisores de 35.640 são: 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 18, 20, 22, 24, 27, 30, 33, 36, 40, 44, 45, 54, 55, 60, 66, 72, 81, 88, 90, 99, 108, 110, 120, 132, 135, 162, 165, 180, 198, 216, 220, 264, 270, 297, 324, 330, 360, 396, 405, 440, 495, 540, 594, 648, 660, 792, 810, 891, 990, 1.080, 1.188, 1.320, 1.485, 1.620, 1.782, 1.980, 2.376, 2.970, 3.240, 3.564, 3.960, 4.455, 5.940, 7.128, 8.910, 11.880, 17.820, 35.640.

3. Lista de todos os divisores comuns: 1, 2, 3, 4, 6, 8, 9, 11, 12, 18, 22, 24, 27, 33, 36, 44, 54, 66, 72, 88, 99, 108, 132, 198, 216, 264, 297, 396, 594, 792, 1.188, 2.376.

4. O resultado final é: 2.376.

Como você pode ver, quanto maior o número de fatores, mais demorado fica o procedimento, e é fácil cometer um erro. Vale a pena saber como esse método funciona, mas, em vez disso, recomendamos que você use nossa calculadora de MDC apenas para ter certeza de que o resultado está correto.

Outro procedimento usado pela nossa calculadora de MDC é a fatoração de primos, que você também pode obter usando a calculadora de fatoração de números primos 🇺🇸, dedicada apenas a isso. Esse método está um pouco relacionado ao mencionado anteriormente. Em vez de listar todos os fatores possíveis, encontramos apenas aqueles que são números primos. Como resultado, o produto de todos os números primos compartilhados é a resposta para o nosso problema e, o que é mais importante, há sempre uma maneira única de fatorar qualquer número para números primos. Então, agora, vamos encontrar o maior denominador comum de 72 e 40 usando a fatoração de primos:

1. Os divisores primos de 72 são: 2, 2, 2, 3, 3.

2. Os divisores primos de 40 são: 2, 2, 2, 5.

3. Em outras palavras, podemos escrever: 72 = 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 3 e 40 = 2 ⋅ 2 ⋅ 2 ⋅ 5.

4. A parte que é compartilhada em ambos os casos é 2 × 2 × 2 = 8, e esse é o maior divisor comum.

Podemos ver que, para esse simples exemplo de máximo divisor comum, o resultado é consistente com o método anterior. Vamos descobrir se ele funciona igualmente bem para o caso mais complicado. Como calcular o MDC de 33.264 e 35.640?

1. Os fatores primos de 33.264 são: 2, 2, 2, 2, 3, 3, 3, 7, 11.

2. Os fatores primos de 35.640 são: 2, 2, 2, 3, 3, 3, 3, 5, 11.

3. Podemos usar a notação de expoente para escrever produtos como: 33.264 = 2⁴ ⋅ 3³ ⋅ 7 ⋅ 11, 35.640 = 2³ ⋅ 3⁴ ⋅ 5 ⋅ 11.

4. O produto comum dos dois números é 2³ ⋅ 3³ ⋅ 11. Também podemos escrevê-lo de uma forma mais compacta e sofisticada, levando em conta os fatoriais: (3!)³ ⋅ 11. Verifique se a nossa calculadora de MDC fornece a você o mesmo resultado, que é 2.376.

Este é outro dos métodos utilizados pela nossa calculadora de máximo divisor comum. A ideia por trás do algoritmo de Euclides, diz que se o número k é o maior divisor comum dos números A e B, então k também é o MDC para a diferença desses números A - B. Seguindo esse procedimento, finalmente chegaremos a 0. Como resultado, o maior divisor comum é o último número diferente de zero. Vamos dar uma olhada em nosso exemplo de MDC mais uma vez: os números 40 e 72. Toda vez que fazemos uma subtração, comparamos dois números, ordenando-os do maior para o menor valor:

• MDC de 72 e 40: a diferença 72 - 40 é igual a 32,
• MDC de 40 e 32: 40 - 32 = 8,
• MDC de 32 e 8: 32 - 8 = 24,
• MDC de 24 e 8: 24 - 8 = 16,
• MDC de 16 e 8: 16 - 8 = 8,
• MDC de 8 e 8: 8 - 8 = 0 Para por aqui!

Em nossa última etapa, obtemos 0 por meio da subtração. Isso significa que encontramos nosso maior divisor comum e seu valor na penúltima linha das subtrações: 8.

E quanto a um caso mais difícil com 33.264 e 35.640? Tentemos resolvê-lo usando o algoritmo euclidiano:

• MDC de 35.640 e 33.264: 35.640 - 33.264 = 2.376,
• MDC de 33.264 e 2.376: 33.264 - 2.376 = 30.888,
• MDC de 30.888 e 2.376: 30.888 - 2.376 = 28.512,
• MDC de 28.512 e 2.376: 28.512 - 2.376 = 26.136,
• MDC de 26.136 e 2.376: 26.136 - 2.376 = 23.760,
• MDC de 23.760 e 2.376: 23.760 - 2.376 = 21.384,
• MDC de 21.384 e 2.376: 21.384 - 2.376 = 19.008,
• MDC de 19.008 e 2.376: 19.008 - 2.376 = 16.632,
• MDC de 16.632 e 2.376: 16.632 - 2.376 = 14.256,
• MDC de 14.256 e 2.376: 14.256 - 2.376 = 11.880,
• MDC de 11.880 e 2.376: 11.880 - 2.376 = 9.504,
• MDC de 9.504 e 2.376: 9.504 - 2.376 = 7.128,
• MDC de 7.128 e 2.376: 7.128 - 2.376 = 4.752,
• MDC de 4.752 e 2.376: 4.752 - 2.376 = 2.376,
• MDC de 2.376 e 2.376: 2.376 - 2.376 = 0 Para por aqui!

Da mesma forma que no exemplo de máximo divisor comum anterior, o MDC de 33.264 e 35.640 é a última diferença diferente de zero no procedimento, que é 2.376.

Como você pode ver, a versão básica dessa calculadora de MDC é muito eficiente e direta, mas tem uma desvantagem significativa. Quanto maior for a diferença entre os números fornecidos, mais etapas serão necessárias para você chegar à etapa final. O módulo é uma operação que encontra o resto da divisão de um número por outro. Portanto, ele é mais eficaz e resolve o problema porque estamos interessados apenas em um resto menor do que os dois números. Você pode aprender mais sobre isso com a nossa calculadora de módulo. Repitamos o algoritmo de Euclides para nossos exemplos de MDC usando o módulo em vez da subtração comum:

• MDC de 72 e 40: 72 mod 40 = 32,
• MDC de 40 e 32: 40 mod 32 = 8,
• MDC de 32 e 8: 32 mod 8 = 0 Pare por aqui!

O maior denominador comum é 8. E quanto ao outro exemplo?

• MDC de 35.640 e 33.264: 35.640 mod 33.264 = 2.376,
• MDC de 33.264 e 2.376: 33.264 mod 2.376 = 0 Pare por aqui!

O MDC de 35.640 e 33.264 é 2.376, e você o encontrou em apenas duas etapas em vez de 15. Bem melhor, não é mesmo?

Se você gosta de operações aritméticas mais simples do que as usadas no algoritmo de Euclides (por exemplo, módulo), a busca binária (ou algoritmo binário, ou de Stein) é definitivamente para você! Tudo o que você precisa usar é comparação, subtração e divisão por 2. Ao calcular o MDC de dois números, nossa calculadora de MDC usa as seguintes identidades:

1. MDC(A, 0) = A, estamos usando o fato de que cada número divide zero e uma observação da última etapa do algoritmo de Euclides, um dos números cai para zero, e nosso resultado foi o anterior.

2. Se ambos A e B forem pares, isso significa que MDC(A, B) = 2 ⋅ MDC(A/2, B/2) devido ao fato de que 2 é um divisor comum.

3. Se apenas um dos números for par, digamos A, então MDC(A, B) = MDC(A/2, B). Desta vez, 2 não é um divisor comum, portanto, podemos continuar com a redução até que ambos os números sejam ímpares.

4. Se ambos A e B forem ímpares e A > B, então MDC(A, B) = MDC((A-B)/2, B). Desta vez, combinamos dois recursos em uma única etapa. O primeiro é derivado do algoritmo de Euclides, calculando o maior divisor comum da diferença de ambos os números e o menor. Em segundo lugar, a divisão por 2 é possível, pois a diferença de dois números ímpares é par e, de acordo com a etapa 3, podemos reduzir o número par.

5. As etapas 2 a 4 são repetidas até você chegar à etapa 1 ou se A = B. O resultado será 2ⁿ ⋅ A, em que n é o número de fatores 2 encontrados em uma segunda etapa.

Como de costume, vamos praticar o algoritmo com nossos conjuntos de números. Começamos com 40 e 72:

• Ambos são pares, portanto MDC(72, 40) = 2 ⋅ MDC(36, 20) = 2² ⋅ MDC(18, 10) = 2³ ⋅ MDC(9, 5) = ...;

• Os números restantes são ímpares, portanto ... = 2³ ⋅ MDC((9-5)/2, 5) = 2³ ⋅ MDC(2, 5);

• 2 é par, portanto, podemos reduzi-lo: ... = 2³ ⋅ MDC(1, 5);

• 1 e 5 são ímpares, portanto: ... = 2³ ⋅ MDC((5-1)/2, 1) = 2³ ⋅ MDC(2, 1); e

• Remova 2 de um número par: ... = 2³ ⋅ MDC(1, 1) = 2³ = 8.

Na verdade, poderíamos ter parado na terceira etapa, já que o MDC de 1 e qualquer número é 1.

Certo, e como encontrar o máximo divisor comum de 33.264 e 35.640 usando o método binário?

• Dois números pares: MDC(35.640, 33.264) = 2 ⋅ MDC(17.820, 16.632) = 2² ⋅ MDC(8.910, 8.316) = 2³ ⋅ MDC(4.455, 4.158) = ....

• Um par e um ímpar: ... = 2³ ⋅ MDC(4.455, 2.079).

• Dois ímpares: ... = 2³ ⋅ MDC((4.455-2.079)/2, 2.079) = 2³ ⋅ ⋅(1.188, 2.079).

• Um par e um ímpar: ... = 2³ ⋅ MDC(594, 2.079) = 2³ ⋅ MDC(297, 2.079).

• Dois ímpares: ... = 2³ ⋅ MDC((2.079-297)/2, 297) = 2³ ⋅ MDC(891, 297).

• Dois ímpares: ... = 2³ ⋅ MDC((891-297)/2, 297) = 2³ ⋅ MDC(297, 297) = 2³ ⋅ 297 = 2.376.

Sabemos que os números primos são aqueles que têm apenas dois divisores inteiros positivos: 1 e ele mesmo. Portanto, a pergunta é: o que são números coprimos? Podemos defini-los como números que não têm divisores comuns. Mais precisamente, 1 é seu único divisor comum, mas como omitimos 1 na fatoração de primos, não há problema em dizer que eles não têm divisores comuns. Em outras palavras, podemos escrever que os números A e B são coprimos se MDC(A,B) = 1. Isso não significa realmente que qualquer um deles seja um número primo, apenas que a lista de fatores compartilhados está vazia. Os exemplos de números coprimos são: 5 e 7, 35 e 48, 23156 e 44613.

Um fato interessante: é possível calcular a probabilidade de dois números escolhidos aleatoriamente serem coprimos. Embora seja bastante complicado, o resultado geral é cerca de 61%. Você ficou surpreso? Faça o teste você mesmo: imagine dois números aleatórios (digamos, com pelo menos 5 dígitos), use nossa calculadora de MDC e descubra se o resultado é 1 ou não. Repita o jogo várias vezes e calcule qual é a porcentagem de números coprimos que você encontrou.

Agora que já conhecemos vários métodos para encontrar o maior divisor comum de dois números, você pode se perguntar: “Como encontrar o maior divisor comum de três ou mais números?”. Acontece que isso não é tão difícil quanto parece à primeira vista. Bem, listar todos os fatores de cada número é definitivamente um método simples, pois você pode encontrar o maior deles. Entretanto, você pode perceber rapidamente que isso consome cada vez mais tempo à medida que o número de números aumenta.

O método de fatoração de primos tem uma desvantagem semelhante, mas, como podemos agrupar todos os primos, por exemplo, em ordem crescente, podemos introduzir uma maneira de chegar a um resultado um pouco mais rápido do que antes.

Por outro lado, se você preferir usar algoritmos binários ou de Euclides para calcular o MDC de vários números, também poderá usar um teorema que afirma isso:

MDC(a, b, c) = MDC(MDC(a, b), c) = MDC(MDC(a, c), b) = MDC(MDC(b, c), a).

Isso significa que podemos calcular o MDC de dois números quaisquer e, em seguida, iniciar o algoritmo novamente usando o resultado com o terceiro número e continuar enquanto houver números restantes. Não importa quais dois números você escolher primeiro.

Outro conceito intimamente relacionado ao MDC é o Mínimo Múltiplo Comum (MMC). Para encontrar o mínimo múltiplo comum, usamos muito do mesmo processo que usamos para encontrar o MDC. Depois de reduzirmos os números à fatoração prima, procuramos a menor potência de cada fator, em vez da maior potência. Em seguida, multiplicamos as potências mais altas e o resultado é o mínimo múltiplo comum ou MMC. Isso pode ser feito manualmente ou com o uso da nossa calculadora de MMC.

O máximo divisor comum pode ser estimado com o uso do MMC também. A expressão a seguir é válida:

MDC(a, b) = |a ⋅ b| / MMC(a, b).

Pode ser útil encontrar o mínimo múltiplo comum primeiro devido à complexidade e à duração. Naturalmente, ele pode ser calculado de qualquer maneira, portanto, vale a pena que você saiba como encontrar o MDC e o MMC.

Já apresentamos algumas propriedades do máximo divisor comum. Nesta seção, listamos as mais importantes:

• Se a razão de dois números a e b (a > b) for um número inteiro, então MDC(a, b) = b.

• MDC(a, 0) = a, usado no algoritmo euclidiano.

• MDC(a, 1) = 1.

• Se a e b não tiverem divisores comuns (são coprimos), então MDC(a, b) = 1.

• Todos os divisores comuns de a e b também são divisores de MDC(a,b).

• Se b ⋅ c / a é um número inteiro e MDC(a, b) = d, então a ⋅ c / d também é um número inteiro.

• Para qualquer número inteiro k: MDC(k⋅a, k⋅b) = k ⋅ MDC(a, b), usado no algoritmo binário.

• Para qualquer número inteiro positivo k: MDC(a/k, b/k) = MDC(a, b) / k.

• MDC(a, b) ⋅ MMC(a, b) = |a ⋅ b|.

• MDC(a, MMC(b, c)) = MMC(MDC(a, b), MDC(a, c)).

• MMC(a, MDC(b, c)) = MDC(MMC(a, b), MMC(a, c)).

Não, o MDC de 14 e 42 não é 2. O MDC de 14 e 42 é 14. Para encontrá-lo, decomponha os dois números em seus divisores:

• Os divisores de 14 são 1, 2, 7 e 14.
• Os divisores de 42 são 1, 2, 3, 6, 7, 14, 21 e 42.

Como você pode ver, o maior número comum em ambas as listas é 14, que é o MDC.

O MDC de 15 e 25 é 5:

1. Escreva todos os divisores de todos os números:

   • Os divisores de 15 são 1, 2, 5, e 15.
   • Os divisores de 25 são 1, 5, e 25.

2. Liste todos os divisores comuns: 1, 5.

3. Pronto! Agora você sabe qual é o máximo divisor comum de 15 e 25! Ele é 5, o maior dos divisores comuns.

O MDC de 24 e 36 é 12. Você pode chegar a essa resposta usando o método de Euclides:

1. Classifique os números em ordem crescente:

   24, 36.

2. Faça a operação de módulo, considerando o maior número como dividendo e o menor como divisor:

   36 mod 24 = 12.

3. Reúna o divisor e o resto e classifique-os em ordem crescente:

   12, 24.

4. Novamente, calcule a operação de módulo da mesma forma:

   24 mod 12 = 0.

5. Só resta um número (o divisor, 12), portanto, 12 é o maior fator comum.

O MDC de 27 e 45 é 9. Você pode usar a fatoração de primos para obter a resposta:

1. Escreva todos os números como um produto de seus fatores primos:

   • 27 = 3 ⋅ 3 ⋅ 3
   • 45 = 3 ⋅ 3 ⋅ 5

2. Liste todos os fatores primos comuns: 3, 3

3. Encontre o produto de todos os fatores primos comuns: 3 ⋅ 3 = 9

4. Pronto! Agora você sabe qual é o maior divisor comum de 27 e 45! Ele é igual a 9.