Calculadora de MDC e MMC
Digite dois números inteiros positivos para encontrar o máximo divisor comum (MDC) usando o algoritmo de Euclides, com cada etapa do cálculo exibida. O mínimo múltiplo comum (MMC) é calculado ao mesmo tempo.
| Máximo divisor comum (MDC) | |
|---|---|
| Mínimo múltiplo comum (MMC) |
Etapas do algoritmo de Euclides
| Fórmula |
|---|
| = × + |
O que é o algoritmo de Euclides?
O algoritmo de Euclides é um método clássico para encontrar o máximo divisor comum de dois inteiros. O procedimento: toma-se o resto da divisão do número maior pelo menor, e repete-se a mesma operação com o divisor e esse resto. Quando o resto chega a 0, o divisor naquele ponto é o máximo divisor comum. Isso permite encontrar o MDC até de números muito grandes com relativamente poucas etapas. Está registrado nos "Elementos" de Euclides, de cerca de 300 a.C., o que o torna um dos algoritmos mais antigos ainda em uso hoje.
Dicas
- O mínimo múltiplo comum (MMC) pode ser encontrado com a fórmula "A × B ÷ MDC". É comumente usado para encontrar um denominador comum entre frações, ou para descobrir quando vários eventos com períodos diferentes vão coincidir.
- Se dois números são coprimos (o MDC deles é 1), o MMC é simplesmente A × B.
- Uma vantagem prática do algoritmo de Euclides é que ele consegue calcular o MDC de números grandes mais rápido do que passando pela fatoração em números primos.
- A ordem em que você digita os dois números não afeta o resultado — o cálculo começa automaticamente pelo maior dos dois.
Perguntas frequentes
Curiosidade — por que um algoritmo de 2.000 anos ainda é usado diariamente
O algoritmo de Euclides aparece no Livro VII dos "Elementos" de Euclides, escritos pelo matemático grego por volta de 300 a.C. É considerado um dos algoritmos mais antigos registrados e, mais de dois mil anos depois, continua sendo um dos primeiros algoritmos apresentados nos livros didáticos de ciência da computação.
O motivo de ter durado tanto tempo está em sua eficiência computacional. Matematicamente, está provado que o número de etapas exigidas pelo algoritmo de Euclides é aproximadamente proporcional à quantidade de dígitos da entrada (o pior caso ocorre com pares de números relacionados à sequência de Fibonacci), o que significa que ele consegue encontrar o MDC até de inteiros enormes em um tempo prático.
A criptografia moderna — a criptografia RSA, por exemplo — ainda usa o cálculo do MDC (ou sua forma estendida, o algoritmo de Euclides estendido) durante a geração de chaves. É uma demonstração marcante da universalidade da matemática que uma descoberta antiga sustente parte da tecnologia que protege a internet hoje.