ZN/pt
ZN.pt · MDC e MMC · zn.pt/mdc-mmc

MDC e MMC

Introduza pelo menos dois números inteiros.

Pelo menos 2, separados por vírgula ou espaço.
Máximo Divisor Comum (MDC)
6
Mínimo Múltiplo Comum (MMC)72
Números considerados3
Comparar

MDC e MMC: algoritmo de Euclides e aplicações práticas

O que são MDC e MMC

O Máximo Divisor Comum (MDC) de dois ou mais inteiros é o maior número inteiro positivo que divide todos eles sem resto. O Mínimo Múltiplo Comum (MMC) é o menor inteiro positivo que é múltiplo de todos eles. Estes dois conceitos são simetricamente úteis em aritmética e teoria dos números — um mede o que os números partilham “por baixo” e o outro “por cima”.

Ambos são conceitos antigos. O algoritmo de Euclides para calcular o MDC, descrito nos Elementos (livro VII, ~300 a.C.), é um dos mais antigos algoritmos matemáticos ainda em uso. É extraordinariamente eficiente — corre em tempo logarítmico no tamanho dos números.

O MDC e o MMC aparecem por todo o lado: simplificar fracções, sincronizar ciclos, dividir volumes em partes iguais, criptografia (o algoritmo RSA depende de MDC), escalonamento de tarefas periódicas em sistemas operativos.

Como se calcula

MDC pelo algoritmo de Euclides

A recursividade é:

MDC(a, b) = MDC(b, a mod b), com MDC(a, 0) = a

Exemplo: MDC(48, 18)

  • 48 mod 18 = 12 → MDC(18, 12)
  • 18 mod 12 = 6 → MDC(12, 6)
  • 12 mod 6 = 0 → MDC(6, 0) = 6

Portanto MDC(48, 18) = 6.

Em pseudocódigo:

função mdc(a, b):
    enquanto b != 0:
        (a, b) = (b, a mod b)
    devolve a

MMC via MDC

Existe uma identidade elegante:

MMC(a, b) = (a × b) / MDC(a, b)

Exemplo: MMC(48, 18) = 48 × 18 / 6 = 864 / 6 = 144.

Por factorização

Alternativamente, factoriza cada número em primos e:

  • MDC = produto dos factores comuns com o menor expoente.
  • MMC = produto de todos os factores presentes (comuns e não comuns) com o maior expoente.

Exemplo: 48 = 2⁴ × 3¹; 18 = 2¹ × 3². Comuns: 2¹ × 3¹ = 6 (MDC). Todos: 2⁴ × 3² = 144 (MMC).

Exemplo prático

Simplificar fracções: reduzir 84/126 à forma irredutível.

  • MDC(84, 126): 126 mod 84 = 42; 84 mod 42 = 0. MDC = 42.
  • 84/126 = 2/3.

Sincronizar cronogramas: um autocarro passa de 15 em 15 minutos numa paragem e outro de 20 em 20 minutos. Se ambos passarem às 08:00, quando voltam a coincidir? MMC(15, 20) = 60. Coincidem a cada 60 minutos — próximo às 09:00.

Distribuição de bens: divides 48 chocolates e 36 rebuçados em sacos idênticos com número máximo de cada. MDC(48, 36) = 12. Fazes 12 sacos com 4 chocolates e 3 rebuçados cada.

Cronogramas de manutenção: um filtro tem de ser mudado de 6 em 6 meses e outro de 8 em 8 meses. MMC(6, 8) = 24. De 24 em 24 meses, os dois são substituídos no mesmo dia — útil para planeamento de peças e serviços.

Aplicações práticas

  • Fracções e razões — reduzir a forma irredutível.
  • Cronogramas cíclicos — encontrar coincidências em ciclos periódicos (manutenção, sinalização).
  • Criptografia RSA — o algoritmo escolhe primos p e q e usa MDC para garantir que a chave pública é coprima com φ(n).
  • Escalonamento de tarefas — sistemas operativos usam MMC para determinar o hyper-periodo de tarefas periódicas.
  • Bézout — a Identidade de Bézout diz que existem inteiros x, y tais que ax + by = MDC(a, b). Base da resolução de equações diofantinas.
  • Códigos musicais — o MDC aparece na análise de ritmos e polirritmos.

Erros comuns

Assumir que MDC(a, b) × MMC(a, b) = a × b só se aplica a dois números. Para três ou mais números, a identidade não é directa — tens de aplicar iterativamente ou usar factorização.

Confundir MDC com maior divisor de um só número. MDC exige pelo menos dois números; o “maior divisor” de um número isolado é ele próprio.

Calcular MMC como o produto. MMC(4, 6) não é 24 — é 12. Só quando os números são coprimos (MDC = 1) é que MMC = produto.

Esquecer o caso zero. MDC(a, 0) = a por convenção. Muitos algoritmos ingénuos entram em loop infinito com b = 0.

Aplicar Euclides a decimais. O algoritmo é para inteiros. Para racionais, é preciso reduzir a fracção primeiro.

Usar factorização em números grandes. Factorizar em primos é exponencial em números muito grandes; o algoritmo de Euclides continua rápido. Para o MDC de 20 dígitos, usa Euclides.

História

O algoritmo de Euclides está descrito nos Elementos, Livro VII, proposições 1 e 2 (~300 a.C.). Foi provado formalmente e é considerado o primeiro algoritmo não-trivial da história da matemática. Corre em tempo O(log(min(a,b))) — surpreendentemente rápido para uma técnica com 2300 anos.

Gabriel Lamé provou em 1844 que o número de passos do algoritmo é limitado por 5× o número de dígitos do menor input. É um teorema clássico da teoria dos algoritmos.

Ver também

Perguntas frequentes

03 entradas
O que é o MDC (Máximo Divisor Comum)?

É o maior número que divide dois ou mais números sem restos. Ex.: MDC(12, 18) = 6 (porque 6 divide ambos, e nenhum número maior divide ambos). Uso: simplificar fracções (12/18 → 2/3 dividindo por 6), agrupar itens em grupos iguais, encontrar ciclos comuns.

O que é o MMC (Mínimo Múltiplo Comum)?

É o menor número que é múltiplo de dois ou mais números. Ex.: MMC(4, 6) = 12. Uso: somar fracções com denominadores diferentes (1/4 + 1/6 = 3/12 + 2/12 = 5/12), sincronizar eventos periódicos, calcular quando dois ciclos coincidem.

Como estão relacionados MDC e MMC?

Para dois números: MDC(a,b) × MMC(a,b) = a × b. Ex.: MDC(12,18) = 6; MMC(12,18) = 36; 6 × 36 = 216 = 12 × 18 ✓. Algoritmo de Euclides calcula MDC eficientemente; MMC deriva-se dele. Truque: se MDC = 1, os números são co-primos e MMC = a × b.

Ver também