O que o algoritmo de Euclides estendido computa?

Ele computa mdc(a, b) exatamente como o algoritmo de Euclides padrão, mas também encontra inteiros x e y (os coeficientes de Bézout) que satisfazem a×x + b×y = mdc(a, b).

O que é a identidade de Bézout?

A identidade de Bézout afirma que para quaisquer dois inteiros a e b, existem inteiros x e y tais que a×x + b×y = mdc(a, b) — o algoritmo de Euclides estendido é a forma padrão de encontrá-los.

Os coeficientes de Bézout são únicos?

Não — se (x, y) é uma solução, então (x + k×(b/mdc), y − k×(a/mdc)) também é uma solução para qualquer inteiro k. Esta calculadora retorna o par específico produzido pelo algoritmo padrão.

a ou b podem ser negativos?

Sim, o algoritmo trata corretamente inteiros negativos; o mdc reportado é sempre retornado como um número não negativo, com x e y ajustados de acordo.

E se a e b forem coprimos?

Se mdc(a, b) = 1, a equação se torna a×x + b×y = 1, o que significa que x é exatamente o inverso multiplicativo modular de a módulo b (e y é o inverso de b módulo a).

Como isso se relaciona com a Calculadora de Inverso Multiplicativo Modular?

A Calculadora de Inverso Multiplicativo Modular executa esse algoritmo exato internamente e extrai x, reduzido módulo m, como resposta — esta calculadora expõe o mdc completo e ambos os coeficientes diretamente.

Quão grandes podem ser a e b?

Esta calculadora suporta inteiros de até 100 dígitos cada, computados com aritmética BigInt exata para que não haja erro de arredondamento de ponto flutuante mesmo para entradas enormes.

Onde o algoritmo de Euclides estendido é usado na vida real?

É usado na geração de chaves RSA, na resolução de equações diofantinas lineares, no cálculo de inversos modulares para protocolos criptográficos, e em qualquer algoritmo que precise de um certificado explícito para um mdc computado.

Calculadora do Algoritmo de Euclides Estendido — Encontre mdc(a,b) e Coeficientes de Bézout

Nossa Calculadora do Algoritmo de Euclides Estendido encontra não apenas mdc(a, b), mas também os inteiros x e y — os coeficientes de Bézout — que satisfazem a identidade a×x + b×y = mdc(a, b), computados com precisão BigInt para entradas arbitrariamente grandes. É o motor direto por trás da Calculadora de Inverso Multiplicativo Modular do site e de inúmeros outros algoritmos de teoria dos números.

Resposta rápida

Esta calculadora encontra mdc(a, b) mais os inteiros x e y que satisfazem a×x + b×y = mdc(a, b), usando o algoritmo de Euclides estendido com precisão BigInt exata.

Digite a e b, depois clique em Calcular.

Como usar Calculadora do Algoritmo de Euclides Estendido — mdc + Coeficientes de Bézout

1
Insira dois inteiros, a e b.
2
Clique em 'Calcular' para encontrar mdc(a, b) e os coeficientes de Bézout x e y.
3
Verifique o resultado: a × x + b × y sempre é igual ao mdc computado.

Por que usar Calculadora do Algoritmo de Euclides Estendido — mdc + Coeficientes de Bézout?

O algoritmo de Euclides comum encontra mdc(a, b) por divisão repetida, mas a versão estendida rastreia informações adicionais a cada etapa para que, ao terminar, também tenha expresso esse mdc como uma combinação linear dos a e b originais — inteiros x e y com a×x + b×y = mdc(a, b), um resultado garantido pela identidade de Bézout. Isso não é apenas uma curiosidade matemática: esses coeficientes são exatamente o que é necessário para calcular inversos multiplicativos modulares, resolver equações diofantinas lineares e implementar a geração de chaves RSA.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Inverso Multiplicativo Modular — Resolva ax ≡ 1 (mod m)

Encontre o inverso multiplicativo modular de a módulo m usando o algoritmo de Euclides estendido. Calculadora gratuita com precisão BigInt e verificação de existência.

Calculadora do Teorema Chinês do Resto — Resolva Sistemas Modulares

Resolva um sistema de congruências x ≡ aᵢ (mod mᵢ) para módulos coprimos entre si usando o Teorema Chinês do Resto. Calculadora gratuita com precisão BigInt.

Calculadora de Exponenciação Modular — bᵉ mod m Rápido Online

Calcule bᵉ mod m para expoentes arbitrariamente grandes usando exponenciação rápida por quadrado-e-multiplicação. Calculadora gratuita com precisão BigInt, essencial para criptografia.

Calculadora de Frações Contínuas — Expanda e Avalie Online

Expanda qualquer número decimal ou fração em seus termos de fração contínua [a₀; a₁, a₂, ...] e veja cada convergente. Calculadora gratuita com precisão exata BigInt.