(Teorema Chinês dos Restos) Sejam
são inteiros dois a dois coprimos, seja
e sejam
os números
para
. Mostre que
é uma solução do sistema
Passo 1
O enunciado nos dá:
- Inteiros
dois a dois coprimos. -
. - Para
definem-se . - Números
quaisquer (restos desejados).
O enunciado propõe a construção
onde
é a função totiente de Euler. O que precisamos mostrar é que, para cada
,
Passo 2
Primeiro observação útil: se
então
é um fator de
. De fato,
e como os
's são dois a dois coprimos, o fator
aparece nesse produto sempre que
. Portanto, para
vale
Consequência: para qualquer inteiro
,
Passo 3
Agora mostro que
. Pelo fato de os
's serem dois a dois coprimos, nenhum dos fatores
com
pode ter fator em comum com
. E
é exatamente o produto de todos esses
com
. Logo
Passo 4
Vou usar o Teorema de Euler (explicando-o de forma simples). O Teorema de Euler afirma que, se
, então
onde
conta os inteiros positivos
que são coprimos com
. Aplicando esse teorema ao par
e
, e lembrando que
(Passo 3), obtemos
Isto significa que o único termo da soma que pode contribuir modulo
é o termo com índice
, e esse termo reduz a
modulo
(veja o próximo passo).
Passo 5
Agora avaliamos
módulo
. Pela definição de
,
Tomando congruência modulo
e usando os resultados dos passos anteriores:
- Para
temos (Passo 2), então . - Para
temos (Passo 4), então .
Somando todas as congruências:
Como isto vale para todo
, concluímos que
satisfaz todas as congruências do sistema simultaneamente.
Passo 6
Tomemos
. Então
,
,
. A construção dá
Verificando:
e
, como desejado.