Calculadora do Teorema do Resto Chinês: Resolver Sistemas Modulares Passo a Passo
Uma calculadora do teorema do resto chinês resolve um sistema de congruências simultâneas — enunciados como x ≡ 2 (mod 3) e x ≡ 3 (mod 5) — combinando-as em uma única congruência módulo o produto (ou mínimo múltiplo comum) dos módulos individuais. O método remonta aproximadamente 1.500 anos atrás ao texto matemático chinês Sunzi Suanjing, e hoje sustenta otimizações de criptografia RSA, cálculos de calendários e códigos corretores de erros, além de ser fundamental em cursos de matemática discreta e teoria dos números. Este guia apresenta como a calculadora funciona internamente, como verificar se um sistema possui solução, como encontrar os inversos modulares dos quais o método depende, dois exemplos completamente desenvolvidos — um com módulos coprimos aos pares e outro sem — além de erros comuns e problemas práticos.
Conteúdo
- 01O que é o Teorema do Resto Chinês?
- 02Como Funciona uma Calculadora do Teorema do Resto Chinês?
- 03Como Verificar se os Módulos São Compatíveis?
- 04O que é um Inverso Modular e Como Encontrar Um?
- 05Exemplo Desenvolvido: Resolver Congruências Coprimes aos Pares
- 06Exemplo Desenvolvido: Reconciliando Módulos Não Coprimos
- 07Reconstruindo a Menor Solução Não Negativa
- 08Quais São os Erros Mais Comuns do Teorema do Resto Chinês?
- 09Problemas Práticos: Teste suas Habilidades de Calculadora do Teorema do Resto Chinês
O que é o Teorema do Resto Chinês?
O Teorema do Resto Chinês (TRC) afirma que, se você tiver um sistema de congruências x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ), e os módulos m₁, m₂, ..., mₙ forem coprimos aos pares (cada par não compartilha fator comum exceto 1), então existe exatamente uma solução para x módulo M, onde M = m₁ × m₂ × ... × mₙ. O teorema recebe seu nome do seu aparecimento conhecido mais antigo no texto chinês do século III ao V Sunzi Suanjing (Manual de Aritmética do Mestre Sun), que apresentava o famoso quebra-cabeça: encontre um número que deixa resto 2 quando dividido por 3, resto 3 quando dividido por 5 e resto 2 quando dividido por 7. Esse quebra-cabeça — e o método TRC que o resolve — reaparece constantemente fora da sala de aula: a criptografia RSA usa TRC para acelerar a descriptografia trabalhando com módulos menores em vez de um gigantesco, cientistas da computação o usam para representar números grandes como tuplas de resíduos menores para aritmética mais rápida, e sistemas de calendário o usam para reconciliar ciclos de comprimentos diferentes (dias da semana, dias do mês e ciclos de anos bissextos).
Teorema do Resto Chinês: para módulos coprimos aos pares m₁, ..., mₙ, o sistema x ≡ aᵢ (mod mᵢ) tem exatamente uma solução módulo M = m₁ × m₂ × ... × mₙ.
Como Funciona uma Calculadora do Teorema do Resto Chinês?
Uma calculadora do teorema do resto chinês automatiza quatro estágios que são tediosos de acompanhar manualmente uma vez que um sistema tem três ou mais congruências, especialmente os cálculos de inverso modular. Internamente, trata cada congruência como um par (aᵢ, mᵢ), confirma que os módulos são utilizáveis juntos e então constrói a solução única usando uma soma ponderada em vez de tentativa e erro. Compreender esses quatro estágios permite verificar a saída da calculadora ou resolver o mesmo problema manualmente em um exame onde nenhuma calculadora é permitida.
1. Passo 1: Verificar os módulos
Confirme que cada par de módulos é coprimo (mdc = 1). Se algum par compartilhar um fator comum, a calculadora muda para a verificação de compatibilidade descrita na próxima seção em vez da fórmula padrão.
2. Passo 2: Calcular o módulo combinado M
Multiplique todos os módulos: M = m₁ × m₂ × ... × mₙ. Este é o módulo da resposta final combinada.
3. Passo 3: Encontrar cada produto parcial e seu inverso modular
Para cada congruência i, calcule Mᵢ = M / mᵢ (o produto de cada módulo exceto mᵢ), então encontre o inverso modular de Mᵢ módulo mᵢ — chame de yᵢ, onde Mᵢ × yᵢ ≡ 1 (mod mᵢ).
4. Passo 4: Combinar e reduzir
Some aᵢ × Mᵢ × yᵢ em cada congruência, então reduza essa soma módulo M para obter a única solução menor não negativa x.
A fórmula por trás de cada calculadora do teorema do resto chinês: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, onde Mᵢ = M/mᵢ e yᵢ é o inverso modular de Mᵢ mod mᵢ.
Como Verificar se os Módulos São Compatíveis?
A versão do livro didático do Teorema do Resto Chinês requer módulos coprimos aos pares, mas sistemas reais — especialmente aqueles que aparecem em problemas de agendamento ou criptografia — frequentemente têm módulos que compartilham fatores. Uma versão generalizada de TRC ainda se aplica, mas apenas se o sistema passar em uma verificação de compatibilidade primeiro: para cada par de congruências x ≡ aᵢ (mod mᵢ) e x ≡ aⱼ (mod mⱼ), as duas devem concordar na sobreposição, o que significa aᵢ ≡ aⱼ (mod mdc(mᵢ, mⱼ)). Se essa verificação falhar mesmo em um único par, o sistema não tem solução alguma, não importa o que mais diga — e uma boa calculadora relata isso em vez de retornar um número errado.
1. Passo 1: Calcular mdc(mᵢ, mⱼ) para cada par de módulos
Para um sistema de duas congruências, há apenas um par para verificar. Para um sistema de três congruências, verifique os três pares.
2. Passo 2: Reduzir ambos os resíduos módulo esse mdc
Tome aᵢ mod mdc(mᵢ, mⱼ) e aⱼ mod mdc(mᵢ, mⱼ). Se corresponderem, o par é compatível.
3. Passo 3: Exemplo de um sistema incompatível
Tome x ≡ 1 (mod 4) e x ≡ 0 (mod 6). mdc(4, 6) = 2. Reduza: 1 mod 2 = 1, e 0 mod 2 = 0. Como 1 ≠ 0, nenhum inteiro satisfaz ambas as congruências — o sistema não tem solução, e uma calculadora do teorema do resto chinês deveria sinalizar exatamente isso em vez de forçar uma resposta.
Regra de compatibilidade para módulos não coprimos: x ≡ aᵢ (mod mᵢ) e x ≡ aⱼ (mod mⱼ) podem ser ambas verdadeiras apenas se aᵢ ≡ aⱼ (mod mdc(mᵢ, mⱼ)).
O que é um Inverso Modular e Como Encontrar Um?
O inverso modular de um número a módulo m é outro número b tal que a × b ≡ 1 (mod m) — desempenha o mesmo papel que 1/a desempenha na divisão ordinária, mas restrito a números inteiros dentro de um módulo fixo. Um inverso modular existe se e somente se mdc(a, m) = 1, o que é exatamente por que o Teorema do Resto Chinês padrão requer módulos coprimos aos pares: garante que cada Mᵢ tenha um inverso mod mᵢ. A maneira mais confiável de encontrar um inverso modular manualmente é o algoritmo euclidiano estendido, que executa o algoritmo mdc ordinário para frente e depois trabalha para trás para expressar 1 como uma combinação de a e m.
1. Passo 1: Executar o algoritmo euclidiano para frente
Encontre o inverso de 4 mod 7. Divida repetidamente: 7 = 1×4 + 3, depois 4 = 1×3 + 1, depois 3 = 3×1 + 0. Os restos são 3, depois 1, depois 0, confirmando mdc(4, 7) = 1, então um inverso existe.
2. Passo 2: Trabalhar para trás para isolar 1
Da penúltima linha, 1 = 4 − 1×3. Substitua 3 = 7 − 1×4 da primeira linha: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. Passo 3: Ler o inverso
A equação 1 = 2×4 − 1×7 significa 2×4 ≡ 1 (mod 7), então o inverso de 4 mod 7 é 2. Verificação rápida: 4 × 2 = 8 = 7 + 1, que é de fato ≡ 1 (mod 7).
Para módulos pequenos, é frequentemente mais rápido testar candidatos diretamente: multiplique a por 1, 2, 3, ... mod m até que o produto seja 1. Para módulos maiores, o algoritmo euclidiano estendido é muito mais confiável.
Exemplo Desenvolvido: Resolver Congruências Coprimes aos Pares
Este é o clássico problema do Sunzi Suanjing: encontre x tal que x ≡ 2 (mod 3), x ≡ 3 (mod 5) e x ≡ 2 (mod 7). Os módulos 3, 5 e 7 são coprimos aos pares, então a fórmula TRC padrão se aplica diretamente.
1. Passo 1: Calcular M
M = 3 × 5 × 7 = 105.
2. Passo 2: Calcular cada Mᵢ e seu inverso
M₁ = 105/3 = 35. 35 mod 3 = 2, e o inverso de 2 mod 3 é 2 (já que 2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, e o inverso de 1 mod 5 é 1. M₃ = 105/7 = 15. 15 mod 7 = 1, e o inverso de 1 mod 7 é 1.
3. Passo 3: Combinar
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. Passo 4: Verificar
23 ÷ 3 = 7 resto 2 ✓. 23 ÷ 5 = 4 resto 3 ✓. 23 ÷ 7 = 3 resto 2 ✓. A menor solução não negativa é x = 23, e toda outra solução é 23 + 105k para qualquer inteiro k.
x ≡ 23 (mod 105) — a mesma resposta que uma calculadora do teorema do resto chinês retorna instantaneamente, e o mesmo quebra-cabeça que abriu este ramo da teoria dos números há mais de mil anos.
Exemplo Desenvolvido: Reconciliando Módulos Não Coprimos
Agora resolva x ≡ 3 (mod 4) e x ≡ 1 (mod 6), onde 4 e 6 não são coprimos (compartilham um fator de 2). A fórmula padrão do exemplo coprimo aos pares não se aplica diretamente, mas o sistema ainda pode ter uma solução única módulo o mínimo múltiplo comum dos módulos, desde que passe na verificação de compatibilidade primeiro.
1. Passo 1: Verificar compatibilidade
mdc(4, 6) = 2. Reduza ambos os resíduos: 3 mod 2 = 1, e 1 mod 2 = 1. Eles correspondem, então o sistema é compatível e uma solução existe.
2. Passo 2: Encontrar o módulo combinado
Em vez de multiplicar 4 × 6 = 24, use o mínimo múltiplo comum: mmc(4, 6) = 12. A solução será única módulo 12, não 24.
3. Passo 3: Substituir e resolver
Escreva x = 4k + 3 a partir da primeira congruência, depois substitua na segunda: 4k + 3 ≡ 1 (mod 6), então 4k ≡ −2 ≡ 4 (mod 6). Ambos os lados e o módulo compartilham um fator de mdc(4, 6) = 2, então divida toda a congruência por 2: 2k ≡ 2 (mod 3). O inverso de 2 mod 3 é 2, então k ≡ 2×2 ≡ 1 (mod 3).
4. Passo 4: Reconstruir x
k = 3j + 1 para qualquer inteiro j, então x = 4(3j + 1) + 3 = 12j + 7. A menor solução não negativa é x = 7.
5. Passo 5: Verificar
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. Então x ≡ 7 (mod 12) está correto, e dividir a congruência pelo fator compartilhado — em vez de ignorá-lo — é o passo que faz o TRC não coprimo funcionar.
Quando os módulos compartilham um fator comum, você não pode usar a fórmula coprima aos pares como está — você deve dividir a congruência resultante por mdc(mᵢ, mⱼ) antes de encontrar o inverso, ou o inverso não existirá.
Reconstruindo a Menor Solução Não Negativa
Cada sistema do teorema do resto chinês que passa em sua verificação de compatibilidade tem infinitas soluções inteiras, não apenas uma — mas todas são congruentes entre si módulo M (ou módulo mmc(m₁, ..., mₙ) no caso não coprimo). Por convenção, uma calculadora relata o menor representante não negativo dessa família infinita, o valor x₀ satisfazendo 0 ≤ x₀ < M, porque é a única resposta canônica mais fácil de estados, comparar e verificar. Toda outra solução é apenas x₀ mais ou menos um múltiplo de M.
1. Reduzindo uma soma intermediária negativa
A soma ponderada no Passo 4 do método da calculadora pode sair negativa se algum resíduo aᵢ for negativo ou se um inverso modular foi calculado como um representante negativo. Se a soma é, digamos, S = −37 e M = 45, adicione M repetidamente até que o resultado seja não negativo: −37 + 45 = 8, então a menor solução não negativa é x₀ = 8, não −37.
2. O conjunto de solução completo
Uma vez que você tem x₀, o conjunto completo de solução é cada inteiro da forma x₀ + kM para k = ..., −2, −1, 0, 1, 2, .... No exemplo do Sunzi acima, isso é 23, 128, 233, ... e também −82, −187, e assim por diante — mas 23 é aquele que você relata a menos que um intervalo específico seja solicitado.
Um resultado intermediário negativo ou muito grande não está errado — ele apenas ainda não foi reduzido. Adicione ou subtraia múltiplos de M até que o valor caia em [0, M).
Quais São os Erros Mais Comuns do Teorema do Resto Chinês?
A maioria dos erros em problemas de TRC vem de pular uma verificação em vez de um cálculo final falho, é por isso que vale a pena desacelerar no início de um problema em vez do final.
1. Aplicar a fórmula coprima a módulos não coprimos
Se algum dois módulos compartilharem um fator, calcular M como seu produto direto e procurar inversos modulares da forma padrão falhará silenciosamente ou produzirá uma resposta errada — sempre verifique mdc(mᵢ, mⱼ) = 1 para cada par primeiro.
2. Confundir um inverso modular com um recíproco regular
O inverso de 4 mod 7 é 2, não 1/4 — inversos modulares são números inteiros encontrados via algoritmo euclidiano estendido (ou multiplicação por tentativa para módulos pequenos), nunca frações.
3. Não reduzir números negativos corretamente módulo m
−2 mod 6 é 4, não −2 e não 2 — continue adicionando o módulo até que o resultado fique no intervalo [0, m). Truncar ou tomar o valor absoluto em vez de adicionar o módulo é uma fonte frequente de respostas erradas.
4. Esquecer de dividir pelo fator compartilhado em sistemas não coprimos
Quando os módulos compartilham um fator comum, uma congruência como 4k ≡ 4 (mod 6) deve ser dividida por mdc(4, 6) = 2 para se tornar 2k ≡ 2 (mod 3) antes que você possa encontrar um inverso — 4 não tem inverso mod 6 em absoluto, já que mdc(4, 6) ≠ 1.
5. Parar antes de reduzir a soma final módulo M
A soma ponderada do Passo 4 (por exemplo, 233 no problema do Sunzi) não é a resposta final — ela deve ser reduzida módulo M (233 mod 105 = 23) para atingir a menor solução não negativa.
Se sua resposta não satisfizer cada congruência original quando você a conectar novamente, recheck a verificação de compatibilidade e os inversos modulares primeiro — é onde quase cada erro de TRC realmente acontece.
Problemas Práticos: Teste suas Habilidades de Calculadora do Teorema do Resto Chinês
Trabalhe esses três sistemas manualmente, verificando coprimalidade aos pares ou compatibilidade primeiro, antes de comparar contra as soluções abaixo. O segundo problema é deliberadamente insolúvel — reconhecer isso é tão importante quanto encontrar uma resposta numérica quando existe.
1. Problema 1 (coprimo aos pares)
Resolva: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). Resposta: M = 105. M₁ = 35 com inverso 2 mod 3; M₂ = 21 com inverso 1 mod 5; M₃ = 15 com inverso 1 mod 7. Soma = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. Verificar: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. Solução: x ≡ 34 (mod 105).
2. Problema 2 (módulos incompatíveis — sem solução)
Resolva: x ≡ 2 (mod 8), x ≡ 5 (mod 12). mdc(8, 12) = 4. Reduza: 2 mod 4 = 2, e 5 mod 4 = 1. Como 2 ≠ 1, o sistema é incompatível e não tem solução — uma calculadora do teorema do resto chinês deve retornar essa conclusão em vez de um número incorreto.
3. Problema 3 (módulos compatíveis não coprimos)
Resolva: x ≡ 5 (mod 9), x ≡ 2 (mod 6). mdc(9, 6) = 3. Reduza: 5 mod 3 = 2, e 2 mod 3 = 2 — compatível. mmc(9, 6) = 18. Escreva x = 9k + 5, substitua: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). Divida por mdc(9, 6) = 3: 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). Então k = 2j + 1, dando x = 9(2j+1) + 5 = 18j + 14. Verificar: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. Solução: x ≡ 14 (mod 18). Se você quiser fazer uma verificação dupla de cada inverso modular e passo de redução em um problema assim, o resolvedor passo a passo de matemática da Solvify o guiará em cada estágio da mesma forma que este guia faz.
A maneira mais rápida de construir fluência real com o Teorema do Resto Chinês é resolver uma mistura de sistemas coprimes, não coprimes mas compatíveis e incompatíveis — reconhecer em que caso você está é metade da habilidade.
Artigos relacionados
Calculadora do Teorema do Resto: Como Encontrar Restos Passo a Passo
Um conceito de resto diferente mas relacionado — este guia cobre o teorema do resto polinomial, contexto útil antes de enfrentar congruências modulares.
Calculadora de Eliminação Gaussiana: Resolver Sistemas Lineares Passo a Passo
Outro método de calculadora sistemático e baseado em algoritmo — compare como eliminação gaussiana e o Teorema do Resto Chinês cada um reduz um sistema para uma única resposta.
Resolução Passo a Passo de Problemas de Matemática: Um Framework Repetível para Qualquer Problema
O framework de 5 passos neste guia se aplica diretamente aos problemas de TRC: identifique o que é dado, escolha um método, trabalhe sistematicamente e verifique o resultado.
Solucionadores matemáticos
Resolvedor de Verificação Inteligente
Tire uma foto de um sistema de congruência ou problema de teoria dos números e obtenha uma solução passo a passo instantânea do Teorema do Resto Chinês.
Soluções Passo a Passo
Veja cada inverso modular, verificação de compatibilidade e passo de redução explicados, não apenas o resíduo final.
Tutor de Matemática IA
Faça perguntas de acompanhamento sobre inversos modulares, módulos coprimos ou por que um sistema não tem solução, com respostas adaptadas ao seu problema exato.
Matérias relacionadas
Fundamentos de Álgebra
O conforto com frações e restos torna aritmética modular e o Teorema do Resto Chinês muito mais fáceis de aprender.
Calculadora de Classificação de Matriz
Outro método de calculadora adjacente à teoria dos números e baseado em algoritmo — prática útil para o mesmo mindset sistemático e passo a passo que TRC requer.