Re: Nicolau e caros colegas deste grupo....

["José Paulo Carneiro" <jpcarneiro@xxxxxxxxxxxxxxx>]

O problema basico eh o seguinte (vou fazer com n=3, mas serve
para qualquer n):
Sao dados 3 numeros naturais a,b,c maiores que 1
e 3 naturais r,s,t tais que 0<=r<a,  0<=s<b, 0<=t<c.
Deseja-se encontrar um inteiro x tal que:
dividido por a deixe resto r;
dividido por b deixe resto s;
dividido por c deixe resto t.

Nao eh dificl verificar que:
1) O problema pode nao ter solucao;
2) Se a, b, c forem 2 a 2 primos entre si, e houver uma solucao y,
entao todas as solucoes sao dadas por  y + k . abc, com k variando
nos inteiros.

O Teorema Chines garante que existe uma (e portanto aquela infinidade
mencionada de solucoes) solucao no caso em que a, b, c sao 2 a 2 primos
entre si.
A demonstracao eh construtiva e baseia-se no fato de que se
u e w forem primos entre si, entao existem inteiros j e k tais que
ju+kw=1 [j e k podem ser achados pelo algoritmo de Euclides; ver
Revista do Professor de Matematica no 37, p.27]. Vamos chamar tal
numero k de Inv(w;u). Agora, uma solucao do problema chines eh:

y= t Inv(ab;c) ab + s Inv(ac;b) ac + r Inv(bc;a) bc

Isto eh tranquilo de verificar. Por exemplo, quando se divide y por a, as
duas
primeiras parcelas deixam resto 0, e a ultima deixa  resto r, ja que
ja+k bc=1, ou seja, k bc eh 1 mais um multiplo de a. Etc.

JP


onde:







-----Mensagem original-----
De: Marcos Eike Tinen dos Santos @ ITA @ <mjsanto@carajasnet.com.br>
Para: obm-l@mat.puc-rio.br <obm-l@mat.puc-rio.br>
Data: Segunda-feira, 17 de Janeiro de 2000 21:05
Assunto: Nicolau e caros colegas deste grupo....


>
>Necessito de algumas ajudas, em questão de prova, resolução de exercícios.
>às vezes tenho dúvidas das minhas provas. Assim, gostaria que aceitasse que
>eu postasse minhas provas aqui, no grupo. Afim, de vocês avaliarem o mesmo.
>
>
>Muito Obrigado!!!!!!
>Caso alguém posso me ajudar a entender o Teorema Chinês dos Restos, ou
>melhor, acho que no Eureka 2. Explicou. Só que num exercícios exemplo, não
>entendi Corretamente.
>
>Muito Obrigado!!!!!!!
>
>