Calculadora de MDC com Algoritmo de Euclides
Ache o máximo divisor comum com cada passo do algoritmo de Euclides, os coeficientes de Bézout x e y, o MMC e o inverso modular, quando existir.
| Etapa | Divisão | Quociente | Resto |
|---|---|---|---|
| mdc(1071, 462) | 1,071 = 2 × 462 + 147 | 2 | 147 |
| mdc(1071, 462) | 462 = 3 × 147 + 21 | 3 | 21 |
| mdc(1071, 462) | 147 = 7 × 21 + 0 | 7 | 0 |
Esta calculadora de MDC acha o máximo divisor comum de dois inteiros com o algoritmo de Euclides e mostra cada passo da divisão, do jeito que os cursos de teoria dos números e de programação o apresentam. Ela também executa o algoritmo estendido para dar os coeficientes de Bézout x e y, com ax + by = mdc(a, b), e o inverso modular quando os números são primos entre si. Acrescente mais inteiros para reduzir uma lista inteira.
Como usar esta ferramenta
- Informe os dois inteiros a e b.
- Se quiser, liste mais inteiros para incluir no MDC e no MMC.
- Leia o MDC e acompanhe os passos de Euclides na tabela.
- Use os coeficientes de Bézout ou o inverso modular para equações diofantinas e exercícios de criptografia.
Fórmula
mdc(a, b) = mdc(b, a mod b), repetido até o resto ser 0
Cada passo troca o número maior pelo resto da divisão dele pelo menor, e o último resto diferente de zero é o MDC. Percorrer os passos de trás para a frente dá inteiros x e y com a·x + b·y = mdc(a, b) — a identidade de Bézout — e mmc(a, b) = |a × b| ÷ mdc(a, b).
Exemplo
Para a = 1071 e b = 462: 1071 = 2 × 462 + 147, depois 462 = 3 × 147 + 21, depois 147 = 7 × 21 + 0. O último resto diferente de zero dá mdc = 21. Substituindo de trás para a frente, 21 = 1071 × (−3) + 462 × 7, então x = −3 e y = 7, e o MMC é 1071 × 462 ÷ 21 = 23.562.
Perguntas frequentes
Por que o algoritmo de Euclides é tão rápido?
O resto cai pelo menos pela metade a cada dois passos, então o número de passos cresce com a quantidade de dígitos, e não com o tamanho dos números. Mesmo entradas de 15 dígitos terminam em bem menos de 100 passos.
O que significa ser primos entre si?
Dois inteiros são primos entre si (ou coprimos) quando o MDC deles é 1, como 8 e 15. Só então a tem inverso módulo b.
Como obtenho um inverso modular daqui?
Quando mdc(a, b) = 1, o coeficiente x satisfaz a·x ≡ 1 (mod b). Para a = 3 e b = 11, o inverso é 4, pois 3 × 4 = 12 = 11 + 1.
O sinal dos números importa?
O MDC de uma lista com algum número diferente de zero é positivo, então mdc(−12, 18) = 6. Os coeficientes de Bézout são ajustados para que a identidade continue valendo com os sinais que você digitou.
Última atualização:
Endereço da página com estes dados: https://kakao.mobile/pt/tools/gcd-calculator/
Citar ou incorporar esta ferramenta
kakaoCalc. (2026, November 9). Calculadora de MDC com Algoritmo de Euclides. https://kakao.mobile/pt/tools/gcd-calculator/
“Calculadora de MDC com Algoritmo de Euclides.” kakaoCalc, 9 Nov. 2026, kakao.mobile/pt/tools/gcd-calculator/.