[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [obm-l] Chines dos Restos para Polinomios
Caros Shine e Morgado:
O problema do artigo do W. Kahan eh que apesar do seu objetivo ser didatico
- faz parte de uma serie de notas de aula pros alunos dele - ele confunde
muito mais do que explica.
Acho que dah pra resumir o artigo numa frase: "Existem demonstracoes
construtivas tanto para o TCR quanto para o TIL e ambas sao baseadas na
determinacao ligeiramente macetosa dos coeficientes de uma dada combinacao
linear de inteiros (TCR) ou polinomios (TIL)"
Ah, Shine! Ateh hoje soh li dois artigos seus (Torre de Hanoi e Grafos e
Contagem Dupla - ambos na Eureka). Achei ambos excelentes. Mas se voce
comecar a se desculpar por artigos ou livros mal-escritos por terceiros, nao
vai te sobrar tempo pra mais nada...pergunta pro Morgado.
Um abraco,
Claudio.
on 24.07.03 16:09, Carlos Yuzo Shine at cyshine@yahoo.com wrote:
> Oi Morgado,
>
> Para ser sincero, eu s? tinha visto o link outro dia e
> achei diferente. N?o li direito, li bem por cima.
> Agora que li, achei meio esquisito sim (eu mesmo n?o
> acharia a f?rmula no teorema chin?s dos restos - eu
> gosto mais das suas aplica??es, como no problema 6 da
> Cone Sul desse ano). Eu sempre achei as duas coisas
> bem diferentes.
>
> Mas achei interessante a demonstra??o n?o indutiva do
> teorema chin?s dos restos (eu s? conhecia a
> demonstra??o por indu??o). Apesar disso, a
> demonstra??o por indu??o tem uma vantagem que ? ajudar
> a entender os casos "zebrosos" (nos quais os m's n?o
> s?o primos dois a dois), o que a demonstra??o do
> artigo n?o cobre bem. Nada contra demonstra??es por
> indu??o (ainda mais vindo de mim, que gosto de teoria
> dos grafos), ? claro, mas achei interessante aprender
> outra demonstra??o.
>
> E no fundo, a parte da analogia usa o que o Claudio
> mostrou e, de fato, ? bem parecida com aquela
> demonstra??o do teorema chin?s.
>
> O que eu acho ? que aquela demonstra??o do teorema
> chin?s foi "inspirada" na demonstra??o de que o
> polin?mio interpolador funciona.
>
> Agora, concordo que aquela parte do final "e se os z's
> n?o s?o todos distintos?" ?, no m?nimo, muito
> esquisita...
>
> De qualquer forma, pe?o desculpas se o artigo n?o tem
> um n?vel de qualidade satisfat?rio.
>
> []'s
> Shine
>
> --- Augusto Cesar de Oliveira Morgado
> <morgado@centroin.com.br> wrote:
>> Shine, voce leu o artigo?
>> Eu e o Claudio lemos e achamos uma !#&?&@$%W*!
>> Morgado
>>
>> Em Thu, 24 Jul 2003 11:23:48 -0700 (PDT), Carlos
>> Yuzo Shine <cyshine@yahoo.com> disse:
>>
>>> Oi Claudio e demais membros da lista,
>>>
>>> Na p?gina do prof. Kahan, de Berkeley, tem um
>> artigo
>>> tra?ando um paralelo entre o teorema chin?s dos
>> restos
>>> e o polin?mio interpolador de Lagrange (em pdf):
>>>
>>>
>>
> http://www.cs.berkeley.edu/~wkahan/MathH90/CRTasLIF.pdf
>>>
>>> []'s
>>> Shine
>>>
>>>
>>> --- Claudio Buffara <claudio.buffara@terra.com.br>
>>> wrote:
>>>> Oi, Pessoal:
>>>>
>>>> Por favor desconsiderem a ultima frase da
>> mensagem
>>>> abaixo. Eu troquei as
>>>> bolas. Realmente, um polinomio p(x) sobre Q[x]
>> ou
>>>> R[x] possui um inverso se
>>>> e somente se p(x) = a, onde a eh um numero
>> (racional
>>>> ou real) nao nulo, ou
>>>> seja, grau(p(x)) = 0.
>>>>
>>>> No entanto, dado um polinomio q(x), primo com
>> p(x),
>>>> existem polinomios r(x)
>>>> e s(x) tais que r(x)*p(x) + s(x)*q(x) = 1
>> (Teorema
>>>> de Bezout para
>>>> polinomios, que pode ser demonstrado de forma
>>>> totalmente analoga ao caso
>>>> inteiro).
>>>>
>>>> Mas isso quer dizer que r(x) eh um inverso de
>> p(x)
>>>> (mod q(x)) e s(x) um
>>>> inverso de q(x) (mod p(x)).
>>>>
>>>> Ou seja, eu confundi os conceitos de inverso
>>>> absoluto com inverso (mod m).
>>>> Nada como uma boa noite de sono pra clarear as
>>>> ideias...
>>>>
>>>> -----
>>>>
>>>> Suponhamos que estejamos trabalhando sobre Q[x]
>> ou
>>>> R[x] ou, em geral, sobre
>>>> F[x] onde F eh um corpo qualquer.
>>>>
>>>> m(x) e n(x) sao primos entre si ==>
>>>> existem m1(x) e n1(x) tais que:
>>>> m(x)*m1(x) == 1 (mod n(x)) e n(x)*n1(x) == 1
>>>> (mod m(x))
>>>>
>>>> Tomemos f(x) = a(x)*n(x)*n1(x) + b(x)*m(x)*m1(x)
>>>>
>>>> Nesse caso:
>>>> f(x) == a(x) (mod m(x)) e f(x) == b(x) (mod
>>>> n(x))
>>>>
>>>> Suponhamos que exista g(x) tal que:
>>>> g(x) == a(x) (mod m(x)) e g(x) == b(x) (mod
>>>> n(x))
>>>>
>>>> Entao teremos:
>>>> f(x) == g(x) (mod m(x)) e f(x) == g(x) (mod
>>>> n(x))
>>>>
>>>> E como m(x) e n(x) sao primos entre si:
>>>> f(x) == g(x) (mod m(x)*n(x))
>>>>
>>>> Ou seja, f(x) eh unico (mod m(x)*n(x)).
>>>>
>>>>
>>>> Um abraco,
>>>> Claudio.
>>>>
>>>>
>>>> *****
>>>>
>>>>
>>>> on 24.07.03 00:30, Claudio Buffara at
>>>> claudio.buffara@terra.com.br wrote:
>>>>
>>>>> Caros colegas da lista:
>>>>>
>>>>> Eh bem sabido que se m e n sao inteiros primos
>>>> entre si, entao o sistema de
>>>>> congruencias:
>>>>> x == a (mod m)
>>>>> x == b (mod n)
>>>>> tem uma solucao unica (mod m*n) para quaisquer
>>>> inteiros a e b.
>>>>> Esse eh justamente o Teorema Chines dos
>> Restos.
>>>>>
>>>>> Um problema que eu resolvi hoje na lista me
>> fez
>>>> pensar numa generalizacao
>>>>> para polinomios:
>>>>> Sejam m(x) e n(x) dois polinomios primos entre
>> si.
>>>>> Dados polinomios quaisquer a(x) e b(x), serah
>> que
>>>> existe um polinomio f(x)
>>>>> que deixe resto a(x) quando dividido por m(x)
>> e
>>>> deixe resto b(x) quando
>>>>> dividido por b(x)?
>>>>> Caso exista, sob que condicoes f(x) serah
>> unico
>>>> (isto eh, unico a menos da
>>>>> adicao de multiplos de m(x)*n(x))?
>>>>> Os resultados acima serao validos tanto em
>> Z[x]
>>>> quanto em Q[x] ou R[x]?
>>>>> E quanto a Z/(p)[x]?
>>>>>
>>>>> A demonstracao padrao (construtiva) do TCR nao
>> se
>>>> estende a aneis de
>>>>> polinomios pois envolve inversos mod m e mod
>> n, os
>>>> quais nao existem se m e
>>>>> n forem polinomios nao constantes.
>>>>>
>>>>> Um abraco,
>>>>> Claudio.
>>>>>
>>>>
>>>>
>>>
>>
> =========================================================================
>>>> Instru??es para entrar na lista, sair da lista e
>>>> usar a lista em
>>>>
>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>>>>
>>>
>>
> =========================================================================
>>>
>>>
>>> __________________________________
>>> Do you Yahoo!?
>>> Yahoo! SiteBuilder - Free, easy-to-use web site
>> design software
>>> http://sitebuilder.yahoo.com
>>>
>>
> =========================================================================
>>> Instru??es para entrar na lista, sair da lista e
>> usar a lista em
>>>
>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>>>
>>
> =========================================================================
>>>
>>>
>>
>>
> =========================================================================
>> Instru??es para entrar na lista, sair da lista e
>> usar a lista em
>> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>>
> =========================================================================
>
>
> __________________________________
> Do you Yahoo!?
> Yahoo! SiteBuilder - Free, easy-to-use web site design software
> http://sitebuilder.yahoo.com
> =========================================================================
> Instru??es para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
> =========================================================================
>
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================