Calculadora do teorema chinês do resto
Resolva congruências simultâneas de uma vez: x ≡ 2 (mod 3), x ≡ 3 (mod 5) e x ≡ 2 (mod 7) têm 23 como menor solução não negativa, e a resposta se repete a cada 105. Útil para lição de casa, olimpíadas e gabaritos. 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
- Restos
- 2, 3, 2
- Módulos
- 3, 5, 7
- X
- 23
- Módulo
- 105
- Produto
- 105
- Quantidade
- 3
Você fornece dois arrays paralelos; o motor verifica a coprimalidade, combina as congruências com CRT sucessivo usando mdc exatos de inteiros e inversos modulares, e informa o representante canônico no intervalo de zero até o produto menos um. O cálculo é aritmética pura de inteiros: sem rede, sem aleatoriedade e sem relógio, portanto os mesmos arrays sempre produzem o mesmo x.
O que o teorema chinês do resto garante para módulos coprimos
O famoso exemplo de sala de aula, x congruente a 2 módulo 3, x congruente a 3 módulo 5 e x congruente a 2 módulo 7, resulta em x igual a 23 módulo 105, e 23 é a menor solução não negativa que esta ferramenta devolve. Esta calculadora exige deliberadamente módulos coprimos dois a dois: quando essa pré-condição é satisfeita, existência e unicidade são garantidas, a resposta é sempre bem definida e a etapa de combinação nunca precisa lidar com fatores compartilhados.
Sistemas cujos módulos não são coprimos dois a dois são rejeitados em vez de resolvidos, o que mantém o contrato simples e honesto.
Como o CRT sucessivo calcula a solução de forma exata e onde é usado
Internamente, o motor parte da primeira congruência e combina repetidamente a seguinte. Dada uma solução parcial x congruente a x0 módulo m e uma nova congruência x congruente a a módulo n, com m e n coprimos, ele calcula o inverso modular de m módulo n com o algoritmo euclidiano estendido, multiplica-o pela diferença reduzida a menos x0 e eleva x0 em m vezes esse passo para obter a nova solução parcial módulo m vezes n.
Estudantes conhecem essa construção quando os livros pedem para reconstruir um número a partir de seus resíduos; professores podem gerar gabaritos para listas de congruências simultâneas sem confiar em calculadoras opacas; desenvolvedores usam o mesmo contrato para validar reconstruções modulares em demonstrações educativas de RSA, onde o CRT com fatores primos coprimos acelera a descriptografia, e para construir vetores de teste determinísticos para bibliotecas de aritmética modular.
Casos de uso
Congruências simultâneas de lição de casa e competições
Resolva sistemas de livros didáticos como x ≡ 2 mod 3, x ≡ 3 mod 5, x ≡ 2 mod 7 e obtenha a menor solução não negativa com o produto dos módulos.
Perguntas frequentes
Os módulos precisam ser coprimos dois a dois?
Sim. Esta calculadora exige módulos coprimos dois a dois, o que garante uma solução única módulo o produto deles.
O algoritmo é randomizado?
Não. Ele usa CRT sucessivo determinístico com mdc exato de inteiros e inversos modulares. Os mesmos restos e módulos sempre produzem a mesma menor solução não negativa.
Os restos podem ser negativos?
Sim. Cada resto negativo é primeiro reduzido pelo próprio módulo, então é tratado como o valor equivalente entre zero e o módulo menos um, e o sistema é resolvido normalmente.
Por que existe uma única resposta abaixo do produto dos módulos?
Porque o teorema garante uma única classe de soluções módulo esse produto quando os módulos são coprimos dois a dois. No exemplo clássico, qualquer outra solução difere de 23 por um múltiplo de 105, então 23 é a menor.
Onde o teorema chinês do resto é usado?
Em exercícios e olimpíadas de teoria dos números, em gabaritos de listas sobre congruências simultâneas e em demonstrações didáticas do RSA, onde dividir o trabalho entre dois fatores primos acelera a decifração.
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/math/chinese-remainder \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"remainders":[2,3,2],"moduli":[3,5,7]}'const res = await fetch("https://api.kit.forhosting.com/math/chinese-remainder", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/math/chinese-remainder",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/math/chinese-remainder", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"remainders":[2,3,2],"moduli":[3,5,7]}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"remainders":[2,3,2],"moduli":[3,5,7]}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/math/chinese-remainder", 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
{
"remainders": [
2,
3,
2
],
"moduli": [
3,
5,
7
]
}Exemplo de resposta
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "math.chinese_remainder",
"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_items | 64 |
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
A calculadora do teorema chinês do resto resolve um sistema de congruências simultâneas — x congruente a cada resto a_i módulo cada módulo n_i — quando os módulos são coprimos dois a dois, e devolve a menor solução não negativa junto com o produto dos módulos. Se algum par de módulos compartilhar um fator comum, a requisição falha com um erro invalid_input claro, em vez de uma resposta adivinhada.
O que o teorema chinês do resto garante para módulos coprimos
O clássico teorema chinês do resto afirma que, se os módulos n_1 até n_k são coprimos dois a dois — ou seja, nenhum par compartilha fator comum maior que um — então existe exatamente uma classe de resíduos módulo o produto de todos os n_i que satisfaz simultaneamente cada congruência x congruente a a_i módulo n_i. Em caso de sucesso, a resposta JSON inclui x, o módulo (que aqui equivale ao produto dos módulos de entrada), o próprio produto, os restos reduzidos ao intervalo canônico de zero até n_i menos um, uma cópia dos módulos e a quantidade de congruências.
Como as entradas são validadas e por que módulos não coprimos são rejeitados
Trata-se de uma escolha deliberada de design, não de uma limitação da matemática: sistemas CRT gerais com fatores compartilhados podem ser inconsistentes e, em vez de mudar silenciosamente de semântica, esta calculadora mantém uma única promessa — módulos coprimos dois a dois na entrada, menor solução não negativa na saída. Os campos aceitos são remainders e moduli, dois arrays JSON de inteiros com o mesmo comprimento, com os aliases a, ai e residues mapeando para remainders, e n, ni e mods mapeando para moduli, de modo que formulários, query strings e notebooks antigos compartilhem um único contrato. Cada entrada pode ser um inteiro JSON ou uma string decimal com sinal inicial opcional; frações, notação científica e espaços embutidos são rejeitados. Cada módulo deve ser um inteiro seguro positivo, os restos podem ser negativos e são reduzidos ao intervalo canônico antes da combinação, e no máximo sessenta e quatro congruências são aceitas por requisição. Antes de qualquer resolução, o motor verifica cada par de módulos com o algoritmo euclidiano do mdc; se algum par tiver mdc maior que um, a requisição falha com invalid_input e uma mensagem que indica o par problemático, por exemplo que o mdc de 4 e 6 é 2. Arrays ausentes, comprimentos diferentes, entradas não inteiras e produtos que excedam a faixa de inteiros seguros também falham com invalid_input, de modo que uma célula errada de planilha nunca se transforma em uma resposta errada silenciosa.
Como o CRT sucessivo calcula a solução de forma exata e onde é usado
Nesta página, o trabalho roda inteiramente no seu navegador de graça; pela API, cada resolução bem-sucedida custa US$ 0,002, a validação que falha não é cobrada e nada é armazenado após o retorno da resposta.
Casos de integração
Demonstrações educativas de RSA e reconstrução modular
Eleve resíduos módulo fatores coprimos de volta a um único inteiro ao explicar acelerações de RSA baseadas em CRT, quebra-cabeças de calendário ou isomorfismos de anéis.
Fixtures de teste determinísticos para bibliotecas modulares
Gere soluções CRT reproduzíveis para testes unitários e asserções de CI sem embutir tabelas calculadas à mão que divergem da implementação.
Perguntas técnicas
Quanto custa a calculadora do teorema chinês do resto?
É gratuita no seu navegador nesta página. Pela API, uma requisição bem-sucedida custa US$ 0,002; entradas inválidas não são cobradas.
O que acontece se os módulos não forem coprimos?
A requisição falha com invalid_input e uma mensagem como 'Moduli are not pairwise coprime: gcd(4, 6) = 2', em vez de adivinhar uma resposta sob uma semântica diferente.
Restos negativos são permitidos?
Sim. Os restos podem ser negativos; eles são reduzidos à faixa de zero até n_i menos um antes da combinação CRT. Os módulos devem ser inteiros positivos.