Calculadora do Teorema Chinês do Resto

Q: Como resolver um sistema de TCR manualmente sem usar a fórmula?

Para duas congruências, você pode usar substituição: tome a primeira, de modo que x = a₁ + k·n₁ para inteiros k. Substitua na segunda congruência, a_1 + k n_1 equiv a_2 ±odn_2, e resolva para k encontrando o inverso de n_1 módulo n_2. Em seguida, substitua k de volta para obter x, e reduza módulo n_1 n_2. Esse método de substituições sucessivas funciona para qualquer número de congruências, resolvendo-as duas de cada vez.

Q: O que acontece se os módulos não forem coprimos dois a dois?

Quando dois módulos compartilham um fator comum, o sistema pode ser inconsistente e não ter solução alguma. Uma solução existe apenas se os restos forem compatíveis: para cada par, a_i equiv a_j ±odgcd(n_i, n_j). Se forem compatíveis, a solução ainda é única, mas apenas módulo o mínimo múltiplo comum dos módulos, em vez do produto deles. A exigência de coprimalidade é o que garante que uma solução sempre exista, e é por isso que esta calculadora rejeita tais entradas.

Q: Por que a solução é única e como encontrar todas as outras soluções?

A unicidade vem do fato de que, se dois números x e x' satisfazem ambos o sistema, a diferença entre eles é divisível por todos os módulos e, portanto, pelo produto N (já que eles são coprimos). Assim, x equiv x' ±odN, o que significa que há exatamente uma solução em 0 ≤ x < N. Todas as outras soluções são x + kN para qualquer inteiro k, incluindo valores negativos como x - N, se o seu problema permitir.

Q: Os restos podem ser negativos ou maiores que o módulo?

Sim. Um resto maior que o seu módulo é automaticamente reduzido — por exemplo, a = 7 com n = 5 é o mesmo que a = 2. Restos negativos também funcionam: x equiv -1 ±od5 significa o mesmo que x equiv 4 ±od5. A resposta final é sempre normalizada para o menor representante não negativo, no intervalo 0 ≤ x < N.

Q: Como encontrar o inverso modular manualmente?

Use o algoritmo euclidiano estendido: execute o algoritmo euclidiano comum em N_i e n_i, depois trabalhe de trás para frente para expressar gcd = 1 como uN_i + vn_i. O coeficiente u satisfaz uN_i equiv 1 ±odn_i, logo y_i = u bmod n_i. Para um módulo primo p, você também pode usar o Pequeno Teorema de Fermat: y_i equiv N_i^p-2 ±odp.

Q: Quais são os erros comuns ao usar o Teorema Chinês do Resto?

Os erros mais frequentes são: usar módulos que não são coprimos dois a dois (por exemplo, 4 e 6, que compartilham o fator 2); trocar os campos de resto e módulo ao introduzir os dados; esquecer que a resposta é uma classe de soluções, não um número único; e introduzir um módulo igual a 1, o que é tecnicamente permitido, mas não acrescenta informação. Verifique também se os seus restos correspondem ao seu problema — x equiv 2 ±od3 não é o mesmo que x equiv 3 ±od2.

Q: Existe uma forma rápida de verificar a resposta da calculadora?

Sim — basta dividir a resposta por cada módulo e conferir os restos. Se o resultado for x, verifique que x bmod n_i = a_i bmod n_i para cada congruência do seu sistema. Uma segunda verificação: calcule x bmod N usando um método diferente, como substituições sucessivas, e confirme que obtém o mesmo valor. Se ambas as verificações passarem, a solução está correta, pois a unicidade módulo N garante que não há outra resposta no intervalo.

Atualizado: 3 outubro 2026

Resolve um sistema de congruências simultâneas usando o Teorema Chinês do Resto. Introduza os restos e os módulos coprimos dois a dois para obter a menor solução não negativa.

Resolvedor do Teorema Chinês do Resto

Fórmula do Teorema Chinês do Resto

Fórmula

\[ x \equiv a_1 \pmod{n_1} \\ x \equiv a_2 \pmod{n_2} \\ \vdots \\ x \equiv a_k \pmod{n_k} \\[1.5em] N = n_1 \cdot n_2 \cdots n_k, \quad N_i = \frac{N}{n_i}, \quad y_i \equiv N_i^{-1} \pmod{n_i} \\[1.5em] x \equiv \sum_{i=1}^{k} a_i \, N_i \, y_i \pmod{N} \]

Onde:

\(a_i\) — os restos (os valores aos quais \(x\) deve ser congruente)
\(n_i\) — os módulos, que devem ser coprimos dois a dois (o máximo divisor comum de quaisquer dois deles é 1)
\(N\) — o produto de todos os módulos, que coincide com o mínimo múltiplo comum quando eles são coprimos
\(N_i\) — o produto de todos os módulos exceto \(n_i\)
\(y_i\) — o inverso modular de \(N_i\) módulo \(n_i\), ou seja, o número tal que \(N_i y_i \equiv 1 \pmod{n_i}\)
\(x\) — a solução única módulo \(N\)

O teorema afirma que, quando os módulos são coprimos dois a dois, o sistema tem exatamente uma solução no intervalo \(0 \le x < N\). A fórmula constrói essa solução combinando cada resto com o inverso do produto parcial correspondente.

Teorema Chinês do Resto – Exemplo de Cálculo

Exemplo: encontrar \(x\) tal que \(x \equiv 2 \pmod{3}\) e \(x \equiv 3 \pmod{5}\) — estes são os valores predefinidos da calculadora.

\[ N = 3 \times 5 = 15 \]

\[ N_1 = \frac{15}{3} = 5, \quad y_1 = 2 \; (\text{pois } 5 \cdot 2 = 10 \equiv 1 \pmod{3}) \]

\[ N_2 = \frac{15}{5} = 3, \quad y_2 = 2 \; (\text{pois } 3 \cdot 2 = 6 \equiv 1 \pmod{5}) \]

\[ x \equiv (2 \cdot 5 \cdot 2) + (3 \cdot 3 \cdot 2) \pmod{15} \equiv 20 + 18 = 38 \equiv 8 \pmod{15} \]

Resultado: \(x = 8\) módulo \(15\). De fato, \(8 \div 3 = 2\) com resto \(2\) e \(8 \div 5 = 1\) com resto \(3\), logo ambas as congruências são satisfeitas. A próxima solução é \(8 + 15 = 23\), depois \(38\), e assim por diante.

Como Usar a Calculadora

Introduza o Número de congruências (no mínimo 2). Mais pares resto/módulo aparecem automaticamente.
Para a primeira congruência, digite o resto em resto 1 (\(a_1\)) e o módulo em módulo 1 (\(n_1\)).
Repita para resto 2 / módulo 2 e quaisquer pares adicionais.
Leia a Menor solução não negativa \(x\) e o Módulo (MMC dos módulos) \(N\). Todo número da forma \(x + kN\) (\(k = 0, 1, 2, \dots\)) também satisfaz o sistema.

O Que É o Teorema Chinês do Resto?

O Teorema Chinês do Resto (TCR) é um resultado clássico da teoria dos números, descrito pela primeira vez pelo matemático chinês Sunzi por volta dos séculos III–V d.C. Ele responde à pergunta: dados vários divisores e os restos deixados ao dividir um número desconhecido por cada um deles, é possível recuperar o número? O teorema diz que sim — desde que os módulos sejam coprimos dois a dois — e a resposta é única dentro de um intervalo cujo comprimento é o produto de todos os módulos.

Uma forma concreta de visualizar: se um cesto contém \(x\) ovos, e contá-los de 3 em 3 deixa 2, enquanto contá-los de 5 em 5 deixa 3, então \(x \equiv 2 \pmod{3}\) e \(x \equiv 3 \pmod{5}\). O TCR determina \(x\) de forma única módulo 15 — neste caso, \(x = 8, 23, 38, \dots\)

O teorema é importante porque mostra que um sistema de muitas congruências pequenas é equivalente a uma única congruência com um módulo grande. Isso permite substituir a aritmética com um módulo enorme por uma aritmética paralela com vários módulos pequenos e convenientes, e depois recombinar os resultados. A etapa de recombinação usa inversos modulares, que você pode calcular separadamente com a calculadora de Inverso Multiplicativo Modular; inversos desse tipo também estão relacionados ao Pequeno Teorema de Fermat e ao Teorema de Euler.

Interpretando o Resultado

A calculadora devolve a menor solução não negativa \(x\) e o módulo combinado \(N\). O conjunto completo de soluções é \(x, x + N, x + 2N, \dots\), e se respostas negativas fizerem sentido no seu problema, \(x - N\) e valores menores também servem. Como a solução é única módulo \(N\), duas entradas diferentes que produzam o mesmo \(x \pmod{N}\) descrevem exatamente o mesmo sistema.

Hipóteses e Limitações

É necessário que os módulos sejam coprimos dois a dois. Cada par de módulos não pode ter nenhum fator comum maior que 1; caso contrário, a calculadora reporta um erro. Se dois módulos forem, por exemplo, 4 e 6 (ambos divisíveis por 2), o sistema pode não ter solução alguma, ou ter várias soluções módulo o seu MMC.
Consistência do sistema. Mesmo com módulos coprimos, o teorema sempre fornece uma solução — essa é a força do TCR. Conflitos entre congruências só podem surgir quando a condição de coprimalidade é violada.
Os restos podem exceder o módulo. Uma entrada como \(a = 7, n = 5\) é tratada como \(7 \equiv 2 \pmod 5\); a calculadora reduz automaticamente a resposta final módulo \(N\).
Os módulos devem ser inteiros positivos. Valores 0 ou negativos são rejeitados.
Sistemas grandes. Como \(N\) é o produto de todos os módulos, ele cresce muito rapidamente. Com muitos módulos, os números envolvidos podem exceder a faixa em que a aritmética de ponto flutuante padrão é exata.

Onde o TCR É Utilizado

Além da teoria dos números pura, o TCR é uma ferramenta de trabalho em várias áreas. Na criptografia, ele acelera a descriptografia RSA calculando o resultado módulo cada fator primo separadamente e recombinando; também sustenta esquemas de limiar como o Shamir's Secret Sharing (Compartilhamento de Segredos de Shamir). Na ciência da computação, ele possibilita sistemas de números residuais que realizam adições e multiplicações em paralelo com módulos pequenos, e aparece em hashing, agendamento e cálculos de calendário — os clássicos problemas de "contar soldados por fileiras" que motivaram originalmente o trabalho de Sunzi.

Perguntas frequentes

Como resolver um sistema de TCR manualmente sem usar a fórmula?

Para duas congruências, você pode usar substituição: tome a primeira, de modo que x = a₁ + k·n₁ para inteiros \(k\). Substitua na segunda congruência, \(a_1 + k n_1 \equiv a_2 \pmod{n_2}\), e resolva para \(k\) encontrando o inverso de \(n_1\) módulo \(n_2\). Em seguida, substitua \(k\) de volta para obter \(x\), e reduza módulo \(n_1 n_2\). Esse método de substituições sucessivas funciona para qualquer número de congruências, resolvendo-as duas de cada vez.

O que acontece se os módulos não forem coprimos dois a dois?

Quando dois módulos compartilham um fator comum, o sistema pode ser inconsistente e não ter solução alguma. Uma solução existe apenas se os restos forem compatíveis: para cada par, \(a_i \equiv a_j \pmod{\gcd(n_i, n_j)}\). Se forem compatíveis, a solução ainda é única, mas apenas módulo o mínimo múltiplo comum dos módulos, em vez do produto deles. A exigência de coprimalidade é o que garante que uma solução sempre exista, e é por isso que esta calculadora rejeita tais entradas.

Por que a solução é única e como encontrar todas as outras soluções?

A unicidade vem do fato de que, se dois números \(x\) e \(x'\) satisfazem ambos o sistema, a diferença entre eles é divisível por todos os módulos e, portanto, pelo produto \(N\) (já que eles são coprimos). Assim, \(x \equiv x' \pmod{N}\), o que significa que há exatamente uma solução em \(0 \le x < N\). Todas as outras soluções são \(x + kN\) para qualquer inteiro \(k\), incluindo valores negativos como \(x - N\), se o seu problema permitir.

Os restos podem ser negativos ou maiores que o módulo?

Sim. Um resto maior que o seu módulo é automaticamente reduzido — por exemplo, \(a = 7\) com \(n = 5\) é o mesmo que \(a = 2\). Restos negativos também funcionam: \(x \equiv -1 \pmod{5}\) significa o mesmo que \(x \equiv 4 \pmod{5}\). A resposta final é sempre normalizada para o menor representante não negativo, no intervalo \(0 \le x < N\).

Como encontrar o inverso modular manualmente?

Use o algoritmo euclidiano estendido: execute o algoritmo euclidiano comum em \(N_i\) e \(n_i\), depois trabalhe de trás para frente para expressar \(\gcd = 1\) como \(uN_i + vn_i\). O coeficiente \(u\) satisfaz \(uN_i \equiv 1 \pmod{n_i}\), logo \(y_i = u \bmod n_i\). Para um módulo primo \(p\), você também pode usar o Pequeno Teorema de Fermat: \(y_i \equiv N_i^{p-2} \pmod{p}\).

Quais são os erros comuns ao usar o Teorema Chinês do Resto?

Os erros mais frequentes são: usar módulos que não são coprimos dois a dois (por exemplo, 4 e 6, que compartilham o fator 2); trocar os campos de resto e módulo ao introduzir os dados; esquecer que a resposta é uma classe de soluções, não um número único; e introduzir um módulo igual a 1, o que é tecnicamente permitido, mas não acrescenta informação. Verifique também se os seus restos correspondem ao seu problema — \(x \equiv 2 \pmod{3}\) não é o mesmo que \(x \equiv 3 \pmod{2}\).

Existe uma forma rápida de verificar a resposta da calculadora?

Sim — basta dividir a resposta por cada módulo e conferir os restos. Se o resultado for \(x\), verifique que \(x \bmod n_i = a_i \bmod n_i\) para cada congruência do seu sistema. Uma segunda verificação: calcule \(x \bmod N\) usando um método diferente, como substituições sucessivas, e confirme que obtém o mesmo valor. Se ambas as verificações passarem, a solução está correta, pois a unicidade módulo \(N\) garante que não há outra resposta no intervalo.