Calculadora do Teorema Chinês do Resto

Bem-vindo à Calculadora do Teorema Chinês do Resto, uma poderosa ferramenta de teoria dos números que resolve sistemas de congruências simultâneas usando o Teorema Chinês do Resto (TCR). Esteja você estudando aritmética modular, preparando-se para competições de matemática, trabalhando em problemas de criptografia ou explorando a teoria dos números, esta calculadora fornece uma solução completa passo a passo com visualização interativa mostrando como as classes de congruência se alinham na solução única.

O que é o Teorema Chinês do Resto?

O Teorema Chinês do Resto (TCR) é um resultado fundamental na teoria dos números que garante a existência e a unicidade de uma solução para um sistema de congruências simultâneas, desde que os módulos sejam coprimos entre si. O teorema foi descrito pela primeira vez pelo matemático chinês Sunzi (孫子) em sua obra Sunzi Suanjing (孫子算經) por volta do século III d.C.

Formalmente, dado o sistema:

Se todos os módulos \(m_1, m_2, \ldots, m_k\) forem coprimos entre si (ou seja, \(\gcd(m_i, m_j) = 1\) para todo \(i \neq j\)), então existe uma solução única \(x\) módulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

Como Funciona o Algoritmo do TCR

A prova construtiva fornece o algoritmo usado por esta calculadora:

Passo 1: Calcular M

Calcule o produto de todos os módulos:

Passo 2: Calcular cada Mᵢ

Para cada congruência \(i\), calcule \(M_i = M / m_i\). Este é o produto de todos os módulos, exceto \(m_i\).

Passo 3: Encontrar os Inversos Modulares

Para cada \(i\), encontre \(y_i\) tal que \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) usando o Algoritmo de Euclides Estendido. Como \(M_i\) e \(m_i\) são coprimos (todos os módulos são coprimos entre si), este inverso sempre existe.

Passo 4: Construir a Solução

A solução geral é \(x + k \cdot M\) para qualquer número inteiro \(k\), o que significa que a solução se repete a cada \(M\) inteiros.

Como Usar Esta Calculadora

1. Insira suas congruências: Para cada equação \(x \equiv a \pmod{m}\), insira o resto \(a\) e o módulo \(m\). Comece com 2 congruências e clique em "Adicionar Congruência" para mais (até 10).
2. Verifique seus módulos: Todos os módulos devem ser inteiros positivos ≥ 2 e coprimos entre si. A calculadora verifica isso automaticamente.
3. Clique em "Resolver Sistema": A calculadora aplica o algoritmo do TCR e mostra a solução única junto com o trabalho passo a passo.
4. Revise a visualização: A reta numérica mostra como as classes de congruência de cada equação se interceptam na solução.
5. Verifique: A seção de verificação confirma que a solução satisfaz todas as congruências originais.

Entendendo os Resultados

• Menor Solução Não Negativa (x₀): A solução única no intervalo [0, M−1]
• Solução Geral: Todos os números inteiros da forma x₀ + kM, onde k é qualquer número inteiro
• Tabela de Verificação: Confirma que x₀ mod mᵢ = aᵢ para cada congruência
• Detalhamento Passo a Passo: Mostra Mᵢ, o inverso modular yᵢ e a soma parcial aᵢ·Mᵢ·yᵢ para cada equação
• Reta Numérica: Representação visual de como as classes de resíduos se alinham na solução

Aplicações do Teorema Chinês do Resto

O Problema Clássico de Sunzi

O problema original de Sunzi Suanjing pergunta: "Existem certas coisas cujo número é desconhecido. Se as contarmos de três em três, sobram duas; de cinco em cinco, sobram três; e de sete em sete, sobram duas. Quantas coisas existem?"

Isso se traduz em: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Usando o TCR, a resposta é x = 23 (e mais geralmente, 23 + 105k para qualquer inteiro não negativo k).

Quando o TCR Não se Aplica?

• Módulos não coprimos: Se qualquer par de módulos compartilhar um fator comum maior que 1, o TCR padrão não garante uma solução. Uma solução ainda pode existir se os restos forem compatíveis, mas esta calculadora requer módulos coprimos entre si para o algoritmo padrão.
• Única congruência: O TCR requer pelo menos 2 congruências. Uma única congruência \(x \equiv a \pmod{m}\) já possui a solução trivial x = a.

Algoritmo de Euclides Estendido

O Algoritmo de Euclides Estendido é essencial para o TCR porque ele encontra o inverso modular. Dados os inteiros \(a\) e \(b\), ele encontra os inteiros \(x\) e \(y\) tais que:

Quando \(\gcd(a, b) = 1\), então \(x\) é o inverso modular de \(a\) módulo \(b\), ou seja, \(a \cdot x \equiv 1 \pmod{b}\).

Perguntas Frequentes

O que é o Teorema Chinês do Resto?

O Teorema Chinês do Resto (TCR) afirma que se você tem um sistema de congruências simultâneas x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), onde todos os módulos são coprimos entre si, então existe uma solução única módulo M = m₁ × m₂ × ... × mₖ. Este teorema foi descrito pela primeira vez pelo matemático chinês Sunzi no século III.

O que significa ser coprimo entre si?

Ser coprimo entre si significa que cada par de módulos não compartilha nenhum fator comum além de 1. Por exemplo, {3, 5, 7} são coprimos entre si porque mdc(3,5)=1, mdc(3,7)=1 e mdc(5,7)=1. No entanto, {4, 6, 5} NÃO são coprimos entre si porque mdc(4,6)=2.

Como resolver um sistema de congruências passo a passo?

Para resolver usando o TCR: (1) Verifique se todos os módulos são coprimos entre si. (2) Calcule M = produto de todos os módulos. (3) Para cada congruência, calcule Mᵢ = M/mᵢ. (4) Encontre o inverso modular yᵢ de Mᵢ módulo mᵢ usando o Algoritmo de Euclides Estendido. (5) Calcule a solução x = Σ(aᵢ × Mᵢ × yᵢ) mod M. A solução geral é x + k×M para qualquer número inteiro k.

Quais são as aplicações do Teorema Chinês do Resto?

O TCR tem muitas aplicações práticas: a criptografia RSA o utiliza para decodificação eficiente. A ciência da computação o utiliza para aritmética de números grandes, dividindo os cálculos em partes modulares menores. O processamento de sinais aplica o TCR em códigos de correção de erros. Problemas de agendamento e calendário também utilizam o TCR.

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

Se os módulos não forem coprimos entre si, o TCR padrão não se aplica diretamente. Em alguns casos, uma solução ainda pode existir se certas condições de compatibilidade forem atendidas (os restos devem ser consistentes em relação ao MDC dos módulos não coprimos). Caso contrário, o sistema é inconsistente.

Recursos Adicionais

• Teorema Chinês do Resto - Wikipédia
• Algoritmo de Euclides Estendido - Wikipédia
• Aritmética Modular - Wikipédia