Calculadora de MDC – Máximo Divisor Comum

A calculadora de MDC da Omni avalia o máximo divisor comum entre dois e quinze números diferentes. Continue lendo para encontrar a resposta para a pergunta: "Qual é o maximo divisor comum de determinados números?", conhecer vários métodos para encontrar 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 é o maior fator inteiro presente entre um conjunto de números. Também é conhecido como maior fator comum e maior denominador 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, vamos aprender como encontrar o MDC.

Há vários métodos que ajudam você a encontrar 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:

• Usando a lista de divisores;
• Fatoração de números primos;
• Algoritmo de Euclides;
• Algoritmo binário (algoritmo de Stein); e
• Uso de 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 estimar o máximo divisor comum é encontrar todos os divisores dos números fornecidos. 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, vamos estimar 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 comumente usado é 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 fator comum.

Podemos ver que, para esse exemplo simples, o resultado é consistente com o método anterior. Vamos descobrir se ele funciona igualmente bem para o caso mais complicado. Qual é 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.

A ideia por trás do algoritmo de Euclidez, 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 nossos exemplos 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? Vamos tentar 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 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 desse localizador 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. Vamos repetir o algoritmo de Euclides para nossos exemplos 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), o algoritmo binário (ou algoritmo de Stein) é definitivamente para você! Tudo o que você precisa usar é comparação, subtração e divisão por 2. Ao estimar o maior fator comum de dois números, lembre-se dessas 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 maior fator 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 do máximo divisor comum 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 estimar qual é 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 8 e 12 é 4:

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

   • Os divisores de 8 são 1, 2, 4 e 8.
   • Os divisores de 12 são 1, 2, 3, 4, 6 e 12.

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

3. O máximo divisor comum é o maior deles, que é 4.

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 30 e 54 é 6. 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:

   • 30 = 2 ⋅ 3 ⋅ 5
   • 54 = 2 ⋅ 3 ⋅ 3 ⋅ 3

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

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

4. O maior fator comum é o resultado da etapa anterior. Para 30 e 54 ele é 6.