Calculadora do teorema chinês do resto (TCR) — Resolva congruências simultâneas
Resolva um sistema de congruências simultâneas x ≡ a₁ (mod n₁), x ≡ a₂ (mod n₂)... com o teorema chinês do resto. Verifica automaticamente se os módulos são coprimos entre si e devolve a menor solução não negativa e a solução geral.
Exemplo resolvido: o problema do "número desconhecido" do Sunzi Suanjing
Um problema clássico do Sunzi Suanjing (o "Clássico matemático de Sun Tzu"), um texto aritmético chinês datado de aproximadamente os séculos III a V, frequentemente citado como a origem do teorema chinês do resto. A pergunta "qual número deixa resto 2 ao ser dividido por 3, resto 3 ao ser dividido por 5 e resto 2 ao ser dividido por 7?" tem como resposta 23, módulo 105.
| Condição 1 | x ≡ 2 (mod 3) |
|---|---|
| Condição 2 | x ≡ 3 (mod 5) |
| Condição 3 | x ≡ 2 (mod 7) |
| Solução | x ≡ 23 (mod 105) |
Dicas
- Se os módulos (nᵢ) não forem coprimos entre si, você receberá um erro — por exemplo, mod 4 e mod 6 compartilham o fator 2, então esta calculadora não consegue resolver esse sistema (seria necessário o TCR generalizado).
- Não é preciso reduzir o resto aᵢ você mesmo: mesmo que seja negativo ou maior que nᵢ, a calculadora o normaliza internamente para mod nᵢ antes de resolver.
- Você pode adicionar de 2 a 5 congruências. Isso é útil para quebra-cabeças que exigem que um número satisfaça três ou mais condições periódicas ao mesmo tempo, como o clássico enigma de "adivinhar o número de soldados".
- A solução geral é exibida como x ≡ resultado (mod N): somar qualquer múltiplo de N ao resultado ainda satisfaz todas as congruências originais.
Perguntas frequentes
Curiosidade — De um texto aritmético do século III à aceleração da criptografia RSA
O teorema chinês do resto remonta a um problema do Sunzi Suanjing, um clássico aritmético chinês que se acredita datar de aproximadamente os séculos III a V d.C. Seu famoso enigma do "número desconhecido" — encontrar um número que deixe restos 2, 3 e 2 ao ser dividido por 3, 5 e 7, respectivamente — já capturava a ideia essencial por trás do teorema moderno: reconstruir um número desconhecido a partir de vários restos de divisão.
Uma das aplicações práticas mais importantes do teorema chinês do resto hoje é acelerar a descriptografia RSA. A descriptografia RSA exige elevar um número grande a uma potência módulo um composto n = p × q, onde p e q são primos grandes. Em vez de trabalhar diretamente módulo n, o TCR permite realizar o cálculo de forma independente módulo p e módulo q e depois recombinar os resultados — uma técnica conhecida como CRT-RSA que, em teoria, pode acelerar a descriptografia em quase quatro vezes, e que está implementada em muitas bibliotecas criptográficas.
Esta ferramenta suporta a forma clássica do teorema, que exige que todos os módulos sejam coprimos entre si. Quando os módulos compartilham fatores comuns (por exemplo, mod 4 e mod 6), às vezes ainda existe uma solução, mas determiná-la e calculá-la exige o teorema chinês do resto generalizado, que está fora do escopo desta ferramenta.