Euclides estendido: mdc e coeficientes de Bézout x, y
Para 240 e 46 o máximo divisor comum é 2, e 240 × (−9) + 46 × 47 = 2. Digite dois inteiros e receba o divisor comum, os dois coeficientes de Bézout e a igualdade que comprova o resultado. Grátis no seu navegador.
- Grátis
- Funciona no seu navegador
- Sem cadastro
- Seus dados não saem do seu aparelho
Executar grátis
Exemplo resolvido
- Primeiro inteiro
- 240
- Segundo inteiro
- 46
- MDC
- 2
- X
- -9
- Y
- 47
- Verificação
- 2
O algoritmo de Euclides estendido faz mais do que informar o máximo divisor comum de dois inteiros: também produz coeficientes de Bézout x e y tais que a vezes x mais b vezes y iguala esse mdc. Esses coeficientes aparecem em inversos modulares quando o mdc é um, em provas construtivas de equações diofantinas lineares e em tarefas de criptografia que precisam de uma combinação explícita em vez de um resto nu.
Dos restos aos coeficientes de Bézout
A divisão euclidiana ordinária substitui repetidamente um par (a, b) por (b, a mod b) até o resto ser zero; o último resto não nulo é mdc(a, b). A forma estendida registra como cada resto se escreve como combinação linear inteira das entradas originais. Em cada passo o resto atual é a vezes um coeficiente mais b vezes outro, e quando o algoritmo para esses coeficientes são exatamente os números de Bézout do mdc.
Apresentações em sala costumam usar substituição retroativa a partir da sequência de quocientes; código de produção costuma atualizar de forma iterativa dois pares de coeficientes sem guardar uma pilha de restos. Ambos os caminhos calculam o mesmo objeto matemático: inteiros x e y que satisfazem a*x + b*y = mdc(a, b). O mdc é sempre devolvido como inteiro não negativo, conforme a convenção padrão de bibliotecas e enunciados de competição.
O que você envia e o que recebe de volta
O par zero e zero também é rejeitado, porque mdc(0, 0) é indefinido e nenhum coeficiente produz uma equação significativa. Em sucesso a resposta inclui a e b normalizados, mdc, x, y, um objeto bezout aninhado com os mesmos coeficientes, uma verificação numérica igual a a*x + b*y e uma string de equação como 240*(-9) + 46*(47) = 2.
Checagens típicas: para 240 e 46 o mdc é 2 e uma solução válida é x igual a menos nove com y igual a quarenta e sete; para um par primo com mdc um os coeficientes dão um inverso modular de a módulo b após reduzir x. Casos-limite com um zero e um parceiro não nulo produzem mdc igual ao valor absoluto da entrada não nula e um padrão trivial de coeficientes.
Onde os coeficientes de Bézout aparecem no trabalho real
Programadores de competição resolvem ax + by = c calculando primeiro o mdc e os coeficientes base, depois escalando e parametrizando a solução geral quando o mdc divide c. Estudantes de criptografia recuperam inversos modulares para exemplos RSA de brinquedo e cifras afins quando mdc(a, m) é um lendo o coeficiente de a após redução módulo m. Professores pedem provas construtivas de que dois inteiros são coprimos e precisam de um oráculo determinístico que mostre a combinação, não só um bit de coprimalidade.
Engenheiros de dados e sistemas às vezes precisam de combinações lineares explícitas ao reconciliar horários periódicos ou aritmética de passos. Use a ferramenta do navegador para checar tarefas rapidamente e depois automatize o mesmo contrato quando seu serviço precisar de checagens diofantinas em lote. Se você só precisa do mdc sem coeficientes, esta página ainda atende a essa necessidade e ensina o resultado construtivo mais forte.
Casos de uso
Equações diofantinas lineares
Obtenha uma solução particular (x, y) para a*x + b*y = mdc e depois escale e parametrize ao resolver a*x + b*y = c em competições ou tarefas.
Bloco base do inverso modular
Quando mdc(a, m) = 1, reduza o coeficiente de Bézout de a módulo m para recuperar um inverso modular em exercícios de cripto e teoria dos números.
Perguntas frequentes
O que é o algoritmo de Euclides estendido?
Ele calcula mdc(a, b) e inteiros x, y (coeficientes de Bézout) tais que a*x + b*y iguala esse mdc, rastreando combinações lineares nos passos de resto euclidiano.
Os coeficientes são únicos?
Não. Se (x, y) funciona, também (x + k*(b/g), y − k*(a/g)) para qualquer inteiro k. Esta ferramenta devolve uma solução particular do algoritmo iterativo.
Qual intervalo de inteiros é suportado?
Cada um de a e b deve ser um inteiro com valor absoluto no máximo 9007199254740991 (Number.MAX_SAFE_INTEGER).
Quanto custa?
A ferramenta do navegador é grátis e roda localmente.
Como encontro os coeficientes de Bézout de 240 e 46?
Digite os dois números. O máximo divisor comum é 2 e os coeficientes são −9 e 47, porque 240 × (−9) + 46 × 47 = 2. O resultado traz essa igualdade para você conferir.
Ferramentas relacionadas
Para desenvolvedores — acesso via API
Tudo nesta página está disponível via API. Esta seção é para equipes que querem integrar a ferramenta aos próprios sistemas; quem não precisa disso pode simplesmente usar a ferramenta acima.
Endpoint
Autenticação por token Bearer. Um único POST coloca a tarefa na fila; o resultado chega por webhook ou link assinado.
Chame do seu código
curl -X POST https://api.kit.forhosting.com/numth/extended-euclidean \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"a":240,"b":46}'const res = await fetch("https://api.kit.forhosting.com/numth/extended-euclidean", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"a": 240,
"b": 46
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/numth/extended-euclidean",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"a": 240,
"b": 46
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/extended-euclidean", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"a":240,"b":46}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"a":240,"b":46}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/extended-euclidean", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)Exemplo de requisição
{
"a": 240,
"b": 46
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "numth.extended_euclidean",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}A API é assíncrona: cada chamada devolve um task_id na hora. Se preferir polling, consulte o status a até 1 requisição por segundo.
Preço
Preço publicado, sem tokens nem créditos escondidos. Tarefa que falha não é cobrada.
Limites
max_abs | 9007199254740991 |
Erros
| HTTP | Código | O que significa |
|---|---|---|
401 | unauthorized | Token ausente ou inválido. Confira o header Authorization. |
402 | insufficient_balance | Saldo insuficiente para esta tarefa. Faça uma recarga e tente de novo. |
404 | unknown_type | Esse tipo de tarefa não existe. Confira o campo type no catálogo. |
429 | rate_limited | Muitas requisições em pouco tempo. Espere um instante e tente de novo. |
Notas técnicas
Esta capacidade recebe dois inteiros, rejeita o caso indefinido em que ambos são zero e devolve um JSON estável com mdc, x, y, uma verificação e uma string de equação legível que você pode colar em anotações ou testes.
Dos restos aos coeficientes de Bézout
Este endpoint implementa o caminho iterativo sobre valores absolutos e depois reintroduz sinais para que entradas negativas ainda satisfaçam a identidade.
O que você envia e o que recebe de volta
Forneça inteiros a e b (aliases first ou m para a, e second ou n para b são aceitos). Não inteiros, campos vazios e valores fora do máximo absoluto de inteiros seguros da plataforma são rejeitados com invalid_input e não são cobrados.
Onde os coeficientes de Bézout aparecem no trabalho real
Como a capacidade é um motor de parse puro, não há deriva de modelo, dependência de rede nem estado armazenado: o mesmo par sempre produz o mesmo JSON para uma convenção fixa de coeficientes. O preço da API é a base publicada de US$ 0,002 por item bem-sucedido; validação falha não consome saldo.
Casos de integração
Ensino e verificações automatizadas
Mostre aos alunos a identidade a*x + b*y = mdc com um campo de equação JSON estável e conecte o mesmo contrato a corretores ou fixtures de CI.
Perguntas técnicas
Por que a e b ambos zero são rejeitados?
mdc(0, 0) é indefinido. Não há máximo divisor comum positivo, então a API devolve invalid_input e não cobra.