(Teorema Chinês dos Restos) Sejam m_{1}, m_{2}, \ldots, m_{k} são inteiros dois a dois coprimos, seja M=m_{1} m_{2} \cdots m_{k} e sejam M_{1}, M_{2}, \ldots, M_{k} os números M_{i}=M / m_{i} para i=1,2, \ldots, k. Mostre que x=b_{1} M_{1}^{\varphi\left(m_{1}\right)}+\cdots+ b_{k} M_{k}^{\varphi\left(m_{1}\right)} é uma solução do sistema
x \equiv b_{i}\left(\bmod m_{i}\right), \quad i=1, \ldots, k

Passo 1

O enunciado nos dá:
  • Inteiros m_{1},m_{2},\dots,m_{k} dois a dois coprimos.
  • M = m_{1}m_{2}\cdots m_{k}.
  • Para i=1,\dots,k definem-se M_{i} = M/m_{i}.
  • Números b_{1},\dots,b_{k} quaisquer (restos desejados).
O enunciado propõe a construção
x = b_{1}M_{1}^{\varphi(m_{1})}+\cdots+b_{k}M_{k}^{\varphi(m_{k})},
onde \varphi(\cdot) é a função totiente de Euler. O que precisamos mostrar é que, para cada i=1,\dots,k,
x \equiv b_{i} \pmod{m_{i}}.

Passo 2

Primeiro observação útil: se j\neq i então m_{i} é um fator de M_{j}. De fato,
M_{j}=\frac{M}{m_{j}}=m_{1}\cdots m_{j-1}m_{j+1}\cdots m_{k},
e como os m's são dois a dois coprimos, o fator m_{i} aparece nesse produto sempre que j\neq i. Portanto, para j\neq i vale
M_{j}\equiv 0 \pmod{m_{i}}.
Consequência: para qualquer inteiro t\ge 1,
M_{j}^{t}\equiv 0 \pmod{m_{i}}\quad\text{quando }j\neq i.

Passo 3

Agora mostro que \gcd(M_{i},m_{i})=1. Pelo fato de os m's serem dois a dois coprimos, nenhum dos fatores m_{j} com j\neq i pode ter fator em comum com m_{i}. E M_{i} é exatamente o produto de todos esses m_{j} com j\neq i. Logo
\gcd(M_{i},m_{i})=1.

Passo 4

Vou usar o Teorema de Euler (explicando-o de forma simples). O Teorema de Euler afirma que, se \gcd(a,n)=1, então
a^{\varphi(n)}\equiv 1 \pmod{n},
onde \varphi(n) conta os inteiros positivos \le n que são coprimos com n. Aplicando esse teorema ao par a=M_{i} e n=m_{i}, e lembrando que \gcd(M_{i},m_{i})=1 (Passo 3), obtemos
M_{i}^{\varphi(m_{i})}\equiv 1 \pmod{m_{i}}.
Isto significa que o único termo da soma que pode contribuir modulo m_{i} é o termo com índice i, e esse termo reduz a b_{i} modulo m_{i} (veja o próximo passo).

Passo 5

Agora avaliamos x módulo m_{i}. Pela definição de x,
x = \sum_{j=1}^{k} b_{j}M_{j}^{\varphi(m_{j})}.
Tomando congruência modulo m_{i} e usando os resultados dos passos anteriores:
  • Para j\neq i temos M_{j}^{\varphi(m_{j})}\equiv 0 \pmod{m_{i}} (Passo 2), então b_{j}M_{j}^{\varphi(m_{j})}\equiv 0\pmod{m_{i}}.
  • Para j=i temos M_{i}^{\varphi(m_{i})}\equiv 1\pmod{m_{i}} (Passo 4), então b_{i}M_{i}^{\varphi(m_{i})}\equiv b_{i}\pmod{m_{i}}.
Somando todas as congruências:
x \equiv b_{i} + \sum_{j\neq i} 0 \equiv b_{i} \pmod{m_{i}}.
Como isto vale para todo i=1,\dots,k, concluímos que x satisfaz todas as congruências do sistema simultaneamente.

Passo 6

Tomemos m_{1}=3,\\ m_{2}=5,\\ b_{1}=2,\\ b_{2}=4. Então M=15, M_{1}=5,\\ M_{2}=3, \varphi(3)=2,\\ \varphi(5)=4. A construção dá
x=2\cdot 5^{2}+4\cdot 3^{4}=2\cdot 25 + 4\cdot 81 = 50+324=374.
Verificando: 374\equiv 2\pmod{3} e 374\equiv 4\pmod{5}, como desejado.

Resposta

x=b_{1}M_{1}^{\varphi(m_{1})}+\cdots+b_{k}M_{k}^{\varphi(m_{k})} satisfaz \;x\equiv b_{i}\pmod{m_{i}}\; para todo i=1,\dots,k.

Exercícios relacionados