Simplificação de fração
- Entrada
- MDC(36, 24)
- Saída esperada
- 12
Dividindo os dois pelo MDC 12, 36/24 simplifica para 3/2; nenhum número menor divide os dois ao mesmo tempo.
Carregando ferramenta… / Loading tool…
MDC de dois números pelo algoritmo de Euclides
O algoritmo de Euclides calcula MDC(a, b) em O(log min(a,b)) passos trocando repetidamente o par (a, b) por (b, a mod b) até o resto zerar. É um dos algoritmos mais antigos da matemática, descrito por Euclides por volta de 300 a.C., e ainda o método mais rápido conhecido para o problema.
Dividindo os dois pelo MDC 12, 36/24 simplifica para 3/2; nenhum número menor divide os dois ao mesmo tempo.
Os dois são primos, então o único divisor comum possível é 1: MDC = 1 confirma que são coprimos.
9 divisões até zerar o resto, o máximo para números de 2 algarismos, porque 89 e 55 são Fibonacci consecutivos.
MDC (Máximo Divisor Comum) é o maior número inteiro positivo que divide todos os números do conjunto sem deixar resto. Ele pode ser encontrado pelo algoritmo de Euclides ou comparando as fatorações primas e tomando a menor potência de cada primo comum. Por exemplo, MDC(12, 18) = 6.
São dois inteiros cujo único divisor positivo em comum é 1, como 8 e 9: nenhum número maior que 1 divide os dois. Também são chamados de primos entre si, mesmo quando nenhum dos dois é primo isoladamente.
No máximo 5 vezes a quantidade de algarismos do menor número, pelo teorema de Lamé (1844); o pior caso real acontece com pares de números de Fibonacci consecutivos, como 89 e 55, que exigem o número máximo de divisões possível para o tamanho deles.
Não: ela exige inteiros positivos maiores que zero, até 10³⁰ cada. Matematicamente MDC(a, 0) = a, mas a ferramenta rejeita zero e negativos para evitar entradas ambíguas, mostrando um erro específico para cada caso.
Números
Os valores ficam apenas no navegador. Nenhum dado é enviado ao servidor.